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.
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)
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