然而,似乎RegEx的初始接受状态是{00,1,^},最终接受状态也是{00,^}.所以交换它们只会导致完全相同的RegEx和DFA,这似乎是矛盾的.
我做错了什么或者这个RegEx应该没有一个真正的补充？
谢谢
I know that to convert a DFA,M to the complement,M`,I just need to swap the initial accepting states and final accepting states.
它不是补充,但你正在做一些与语言相反的事情和regular languages are closure under reversal.
DFA的冲销
什么是反转语言？
语言L的反转(表示为LR)是由…组成的语言
所有字符串的颠倒
鉴于L是一些FA A的L(A),我们可以为LR构建一个自动机：
reverse all edges (arcs) in the transition diagram
the accepting state for the LR automaton is the start state for A
create a new start state for the new automaton with epsilon transitions to each of the accept states for A
注意：通过反转所有箭头和交换DFA的初始和接受状态的角色,您可以获得NFA.
这就是为什么我写FA(不是DFA)
补充DFA
Finding the complement of a DFA?
定义：语言的补语根据与Σ*(西格玛星)的集合差异来定义.即L’=Σ* – L.
而L的补码语言(L’)除了^中的字符串之外,所有字符串均来自Σ*(西格玛星).Σ*是字母表中的所有字符串.
Σ=语言符号集
To construct the DFA D that accepts the complement of L,simply convert
each accepting state in A into a non-accepting state in D and convert
each non-accepting state in A into an accept state in D.
(Warning! This is not true for NFA’s)
A是L的DFA,D是补码
注意：为了构建补充DFA,旧的DFA必须是一个完整的手段,所有这些都应该从每个状态(或换句话说δ should be a complete function)都可能出现.
Complement: reference with example
Complement DFA for Regular Expression
(00+1)*
以下是DFA名为A：
但DFA并不是DFA完整版.过渡函数δ是部分定义的,但不适用于全域Q×Σ(从l1向上偏离q1的边缘).
其完整的DFA可以如下(A)：
在上述DFA中,定义了所有可能的事务(*对于每对Q,Σ*),δ在这种情况下是一个完整的函数.
Reff: to learn what is Partial Function.
可以通过将所有最终状态q0更改为不是最终状态来构建新的补充DFA D,反之亦然.
所以在补数q0变成非最终和q1,q2是最终状态.
现在,您可以使用ARDEN’S THEOREM and DFA给出补全语言的正则表达式.
在这里我正在直接写正则表达式：
(00 1)* 0(^ 1(1 0)*)
其中^是空符号.
一些有用的链接：
从here,通过我的个人资料,您可以在FA找到一些更有用的答案.另外,两种常规语言属性的良好链接：one,second
