Finding the complement of a DFA?

问题:

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

回答1:

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 L^R) 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 L^R:

• reverse all edges (arcs) in the transition diagram

• the accepting state for the L^R 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

回答2:

I didn't take the time to read all of Grijesh's answer, but here's the simple way to get a DFA accepting the complement of a language, given a DFA accepting the language: use the same DFA, but change accepting states to non-accepting, and vice-versa.

Strings previously accepted will be rejected, and strings previously rejected will be accepted. Since all transitions must be defined in any valid DFA, and since all input strings lead to exactly one state, this always works.

To get a DFA for the reversal, you can first construct an NFA by adding a new initial state that branches non-deterministically to all of the accepting states of the original DFA. Reverse all the transitions of the original DFA, and make the only accepting state be the initial state of the original DFA.