问正则表达式的补码如何查找

EN

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

使用有限自动机表示法可以最容易地构建正则表达式的补集。如下图所示：

​

​

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

现在，您已经完成了一半，但是现在您需要从它构建一个正则表达式。这在你的课本或同等的书中肯定有解释，但如果你找不到，here是一个描述算法的pdf。

使用(A =状态1)和(F =状态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)*

简单地说，就是：

• 任意多个0
• 一(！)
• 和任意多个0或1

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

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

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