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