regex - 正则表达式的补码怎么找

Question

给出语言 L 在字母表 {0,1} 上的正则表达式，其补码由正则表达式 0* 表示

我认为答案是 1^+ 但我无法证明请帮忙

Answer 1

首先，丹尼尔是正确的，答案是“所有至少包含一个 1 的单词”。但是你怎么证明呢？

使用有限自动化表示可以最容易地构建正则表达式的补码。见下图：

左框显示 的 DFA 0*。要构建它的补充，您需要做的就是让所有非接受状态都接受状态，反之亦然。这是在正确的图像中完成的。

现在，您已经完成了一半，但现在您需要从中构建一个正则表达式。这肯定在您的教科书或同等材料中进行了解释，但如果您没有找到它，这里有一个描述该算法的 pdf。

使用提供的算法，在 (A = state 1) 和 (F = state 2) 的情况下，您会得到：

R_11^0 = ɛ|0
R_12^0 = 1
R_21^0 = (empty set)
R_22^0 = ɛ|0|1

继续 R_ij^1，你会得到：

R_11^1 = (ɛ|0) | (ɛ|0)(ɛ|0)*(ɛ|0) = (ɛ|0)* = 0*
R_12^1 = 1 | (ɛ|0)(ɛ|0)*1 = 1 | 0+1 = 0*1
R_21^1 = (empty set) | (empty set)(ɛ|0)*(ɛ|0) = (empty set)
R_22^1 = (ɛ|0|1) | (empty set)(ɛ|0)*1 = (ɛ|0|1)

最后阶段：

R_11^2 = 0* | (0*1)(0|1)*(empty set) = 0*
R_12^2 = 0*1 | (0*1)(ɛ|0|1)*(ɛ|0|1) = (0*1)(0|1)* = 0*1(0|1)*   <------- !!! HERE !!!
R_21^2 = (empty set) | (ɛ|0|1)(ɛ|0|1)*(empty set) = (empty set)
R_22^2 = (ɛ|0|1) | (ɛ|0|1)(ɛ|0|1)*(ɛ|0|1) = (ɛ|0|1)

现在，您可以通过查看所有以起始状态为第一个索引、以接受状态为最后一个索引的结果来找到正则表达式。在我们的示例中，状态 1 (A) 是唯一的开始状态，状态 2 (F) 是唯一的接受状态，因此您的结果是R_12^2：

0*1(0|1)*

用简单的英语来说，就是：

• 尽可能多的零
• 一个（！）
• 和尽可能多的零或一

所以换句话说，它是所有至少包含一个单词的单词。

Answer 2

正则表达式的补码可以通过从正则表达式中生成 NFA，然后将其转换为 DFA（如果可能，使其成为最小 DFA）来确定。使用 Arden 定理找到非最终状态的正则表达式，这是您对语言的补充。

Answer 3

语言的补语 ( ^0*$) 包含空词和所有仅由零组成的词。因此，该语言包含所有不只由零组成的单词，即至少包含一个单一的单词。因此，该语言的正则表达式是^.*1.*$。考虑到字母表，并将正则表达式中的第一个设为第一个，这相当于^0*1(0|1)*$.