Gri*_*han 32
正如你所说的那样:
我知道要将DFA,M转换为补码,M`,我只需要交换初始接受状态和最终接受状态.
撤销DFA
什么是逆转语言？
语言L(表示为L R)的逆转是由L 中所有字符串的反转组成的语言.
鉴于某些FA A的L是L(A),我们可以为L R构造一个自动机:
反转转换图中的所有边(弧)
L R自动机的接受状态是A的开始状态
为新自动机创建一个新的开始状态,epsilon转换为A的每个接受状态
注意:通过反转其所有箭头并交换DFA的初始和接受状态的角色,您可能会获得NFA.
这就是我写FA(不是DFA)的原因
补充DFA
找到DFA的补充？
Defination:语言的补语是根据与Σ*(西格玛星)的集合差异来定义的.那是L ' =Σ * - L.
并且L的补语(L ')具有来自Σ*(sigma star)的所有字符串,除了L.Σ*中的字符串是字母表Σ上的所有可能的字符串.
Σ=语言符号集
要构造接受L的补码的DFA D,只需将A中的每个接受状态转换为D中的非接受状态,并将A中的每个非接受状态转换为D中的接受状态.
(警告!这不是真的对于NFA的)
A是L的DFA,D是补体
注意:要构建补充DFA,旧的DFA必须是一个完整的手段,每个州都应该有可能的边缘(或者换句话说,?应该是一个完整的函数).
补充正则表达式的DFA
(00+1)*
以下是名为A的 DFA :
但是这个DFA不是完整的DFA.转换函数?是部分定义的,但不适用于完整的域Q×?(错过了标签的q1前沿1).
其完整的DFA可以如下(A):
在上面的DFA中,定义了所有可能的事务(每对Q,?*都是*),?在这种情况下是一个完整的函数.
可以通过将所有最终状态改变为非最终状态来构造新补码DFA D,q0反之亦然.
因此补充q0变为非q1, q2最终状态并且是最终状态.
现在,您可以使用ARDEN'S THEOREM和我给出的DFA为补充语言编写正则表达式.
在这里,我直接写补充正则表达式:
(00 + 1)* 0 (^ + 1(1 + 0)*)
其中^是null符号.
一些有用的链接:
从这里和通过我的个人资料,你可以找到一些更有用的答案在FA.另外,关于常规语言属性的两个很好的链接:一,二