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**

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.