寻找DFA的补充? [英] Finding the complement of a DFA?
问题描述
要求我显示DFA图和RegEx，作为RegEx (00 + 1)*的补充.在前面的问题中，我不得不证明DFA的补码是封闭的并且也是正则表达式，因此我知道要将DFA M转换为补码M`，我只需要交换初始接受状态，然后最终接受状态.
但是，似乎RegEx的初始接受状态为{00, 1, ^}，最终接受状态也为{00, 1, ^}.因此，交换它们只会导致RegEx和DFA完全相同，这似乎是矛盾的.
我做错什么了吗?或者说RegEx应该没有真正的补充吗?
谢谢
正如您所说的那样:
我知道要将DFA M转换为补码M`，我只需要交换初始接受状态和最终接受状态.
其不是补语，但是您正在做某种相反的语言和 δ应该是完整的功能) .
正则表达式
的DFA补充(00+1)*
以下是名为 A 的DFA:
但该DFA并非完整的DFA.过渡函数δ是部分定义的，但不是为完整域Q×Σ定义的(对于1 标签，缺少q1的上升沿).
其完整的DFA可以如下( A ):
在上述DFA中，定义了所有可能的事务(*对于每对Q,Σ *)，在这种情况下δ是完整功能.
可以通过将所有最终状态q0更改为非最终状态来构造新的补充DFA D ，反之亦然.
因此，补码q0变为非最终状态，而q1, q2为最终状态.
现在，您可以使用此处，通过我的个人资料，您可以找到关于FA的更多有用答案.另外，还有两个关于常规语言属性的良好链接: 一个 ， 秒
I am asked to show DFA diagram and RegEx for the complement of the RegEx (00 + 1)*. In the previous problem I had to prove that the complement of a DFA is closed and is a regular expression also, so 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.
However, it appears that the initial accepting states for the RegEx are {00, 1, ^} and the final accepting states are {00, 1, ^} as well. So swapping them will just result in the exact same RegEx and DFA which seems contradictory.
Am I doing something wrong or is this RegEx supposed to not have a real complement?
Thank you
As you says in question:
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.
Its not complement, but you are doing something like reverse of a language and regular languages are closure under reversal.
Reversal of DFA
What is the Reversal Language ?
The reversal of a language L (denoted LR) is the language consisting of the reversal of all strings in L.
Given that L is L(A) for some FA A, we can construct an automaton for 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
Note: By reversing all its arrows and exchanging the roles of initial and accepting states of a DFA you may get an NFA instead.
that's why I written FA(not DFA)
Complement DFA
Finding the complement of a DFA?
Defination: The complement of a language is defined in terms of set difference from Σ* (sigma star). that is L' = Σ* - L.
And the complement language (L') of L has all strings from Σ* (sigma star) except the strings in L. Σ* is all possible strings over the alphabet Σ.
Σ = Set of language symbols
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 is DFA of L, D is for complement
Note: To construct complement DFA, old DFA must be a complete means there should all possible out going edge from each state(or in other words δ should be a complete function).
Complement: reference with example
Complement DFA for Regular Expression
(00+1)*
below is DFA named A:
But not this DFA is not complete DFA. transition function δ is partially defined but not for full domain Q×Σ (missing out going edge from q1 for lable 1).
Its complete DFA can be as follows (A):
In the above DFA, all possible transactions are defined (*for every pair of Q,Σ *) and δ is a complete function in this case.
Reff: to learn what is Partial Function.
New complement DFA D can be constructed by changing all final states q0 to not final states and vice-versa.
So in complement q0 become non-final and q1, q2 are the final states.
Now you can write Regular expression for complement language using ARDEN'S THEOREM and DFA I given.
Here I am writing Regular Expression for complement directly:
(00 + 1)* 0 (^ + 1(1 + 0)*)
where ^ is null symbol.
some helpful links:
From here and through my profile you can find some more helpful answers on FA. Also, two good links on properties of regular language: one, second
这篇关于寻找DFA的补充?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
