查找DFA的补？(Finding the complement of a DFA?)

我要求出示DFA图和正则表达式正则表达式的补(00 + 1)* 。 在前面的问题，我必须证明一个DFA的补被关闭，是一个正则表达式还，所以我知道到DFA，男转换为补充，M`，我只需要交换初始接受状态和最终的接受状态。

然而，看来对于正则表达式的初始接受状态是{00, 1, ^}和最终接受状态是{00, 1, ^}为好。 所以交换他们只会导致完全相同的正则表达式和DFA这似乎是矛盾的。

我是不是做错了什么，或者这个表达式应该不会有真正的补充？

谢谢

Answer 1:

当你有问题说：

我知道，一个DFA，男转换为补充，M`，我只需要交换初始接受状态，并最终接受状态。

它不是补充 ，而是你正在做的事情就像语言和反向 正规语言正在逆转关闭 。

DFA逆转

什么是逆转的语言？

语言L（表示为L ^R）的反转是由在L.所有串的反转的语言

鉴于L是对于一些FA A L（A）中，我们可以构建L ^R的自动机：

• 扭转转换图中的所有边（弧线）

• 为L ^R自动机接受状态为开始状态

• 创建用于小量过渡的新自动机一个新的开始状态，每换一个的接受状态

注 ：通过逆转其所有的箭头和交换的初始角色和接受DFA的状态，你可能会得到一个NFA来代替。
_{这就是为什么我写的FA（不DFA）}

补DFA

查找DFA的补？

Defination:语言的补从Σ*（SIGMA星）差集的定义。 即^L'=Σ* - L.

和L的补语言^（L'）具有从Σ*（SIGMA星）除L.Σ*字符串的所有字符串是在字母表Σ所有可能的字符串。
_{Σ=设置语言符号}

为了构建接受L的补体的DFA d，简单地转换每一个接受状态在A分成在d的非接受状态，并转换A中的每个非接受状态到D.接受状态
（ 警告！这是不正确的NFA的 ）

_{A是或L的DFA，d是用于补}

注意 ：要构建完善DFA，老DFA必须是一个完整的手段应该从每一个状态都可能传出边缘（或者换句话说δ应该是一个完整的功能 ）。

补体：与参考例

补DFA的正则表达式(00+1)*

以下是DFA命名为A：

但是这次不会DFA是不完整的DFA。 转换函数δ是部分地限定而不是全域Q×Σ （ 错过了从Q1向边沿为拉布勒1 ）。

其完整的DFA可以如下（A）：

另外，在上述DFA，所有可能的事务被定义（*每对Q,Σ *）和δ是在这种情况下的完整功能。

R效率：学习什么是部分功能。

新补DFA d可以通过改变所有的最终状态构造q0不最终状态，反之亦然。

因此，在补充q0成为非最终和q1, q2是最终状态。

现在你可以使用写补语言的正则表达式ARDEN定理和DFA给我。

我在这里写了直接补正则表达式：

(00 + 1)* 0 (^ + 1(1 + 0)*)

其中^是空符号。

一些有用的链接 ：
从这里通过我的个人资料，你可以找到一些FA更多有用的答案。 另外，在正规语言的特性两个很好的链接： 一个 ， 第二

Answer 2:

我没有花时间去阅读所有Grijesh的答案，但这里的简单的方法来得到一个DFA接受语言的补充，给出一个DFA接受的语言：使用相同的DFA，但改变接受状态向非接受，和反之亦然。

先前被拒绝以前接受的将被拒绝的字符串和字符串会被接受。 由于所有的转换必须在任何有效的DFA来定义，因为所有的输入字符串导致只有一个状态，这总是工作。

为了得到一个DFA为反转，则可以先加入一个新的初始状态的分支非确定性的所有原始DFA的接受状态的构造NFA。 反向原始DFA的所有转变，使仅接受状态是原始DFA的初始状态。

文章来源: Finding the complement of a DFA?