Finding the complement of a DFA?

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: onesecond

1 thought on “Finding the complement of a DFA?”

  1. whoah this blog is wonderful i really like reading your articles. Keep up the great paintings! You realize, a lot of people are hunting round for this info, you could help them greatly.


Leave a Comment