正如您在问题中所述:
我知道将DFA M转换为补集M`,只需要交换初始接受状态和最终接受状态。
这不是补集,而是你在做一些类似于反转语言的操作,正则语言对于反转是封闭的。
DFA的反转
什么是反转语言?
一个语言L的反转(表示为LR)是由L中所有字符串的反转组成的语言。
假设L是FA A的L(A),我们可以构造一个用于LR的自动机:
注意:通过反转所有箭头并交换 DFA 的初始状态和接受状态,您可以得到一个 NFA。
这就是我写 FA(而不是 DFA)的原因
补集 DFA
如何找到 DFA 的补集?
定义:
语言的补集是通过与 Σ*(sigma star)的差集来定义的,即 L' = Σ* - L。
补集语言(L')是由Σ* (sigma star)中除了L中的字符串组成的。Σ*包含了字母表Σ中所有可能的字符串。
Σ = 语言符号集合
要构建接受补集L的DFA D,只需要将A中的每个接受状态转换为D中的非接受状态,并将A中的每个非接受状态转换为D中的接受状态。
(注意!对于NFA不适用)
A是L的DFA,D是补集
注意:要构建补集DFA,旧的DFA必须是完整的,也就是说每个状态都应该有可能的出边(或者换句话说δ
应该是一个完整的函数)。
补充:附带示例的参考
为正则表达式(00+1)*
构建DFA
下面是名为A的DFA:
但是这个DFA并不完整。转移函数δ是部分定义的,而不是针对完整域Q×Σ(q1缺少标签为1的出边)。它的完整DFA可以如下所示(A):
在上述DFA中,定义了所有可能的转换(*对于每一对*),并且在这种情况下
δ
是一个完全函数。
参考文献:学习什么是部分函数。
通过将所有终止状态
q0
更改为非终止状态,反之亦然,可以构造新的补充DFA
D。
因此,在补充中,
q0
变成非最终状态,
q1,q2
是最终状态。
现在你可以使用我提供的
ARDEN'S THEOREM和DFA编写补集语言的正则表达式。
这里我直接为补集编写正则表达式:
(00 + 1)*
0
(^ + 1(1 + 0)*)
其中
^
是空符号。
一些有用的链接:
你可以从这里和我的个人资料中找到更多关于FA的有用答案。此外,还有两个关于正则语言属性的好链接:一个,第二个