Prerequisite – Design a Finite automta

Suppose we have a DFA that is defined by ( Q, , , q0, F ) and it accepts the language L_{1}. Then, the DFA which accepts the language L_{2} where L_{2} = ̅L_{1}‘, will be defined as below:

( Q, , , q0, Q-F )

The complement of a DFA can be obtained by **making the non-final states as final states and vice-versa**. The language accepted by the complemented DFA L_{2} is the complement of the language L_{1}.

**Example-1:**

L_{1}: set of all strings over {a, b} of even length

L_{1}= {, ab, aa, abaa, aaba, ....}

L_{2}: set of all strings over {a, b} of odd length

L_{2}= { a, b, aab, aaa, bba, bbb, ...}

Here, we can see that L_{2} = ̅L_{1}

Lets first draw the DFA for L_{1} that accepts the strings of even length.

Now, for designing the DFA for L_{2}, we just need to complement the above DFA. We will change the non-final states as final state and the final states as non-final states.

This is our required complemented DFA.

**Example-2:**

L_{1}: set of all strings over {a, b} starting with ‘a’.

L_{1}={ a, ab, aa, aba, aaa, aab, ..}

L_{2}: set of all strings over {a, b} not starting with ‘a’.

L_{2}={ , b, ba, bb, bab, baa, bba, ...}

Here, we can see that L_{2} = ̅L_{1}

Lets first draw the DFA for L_{1} that accepts the set of all strings over {a, b} starting with ‘a’

Now, for designing the DFA for L_{2}, we just need to complement the above DFA. We will change the non-final states as final state and the final states as non-final states.

This is our required complemented DFA that accepts the strings that are not starting with ‘a’.

** Note:** Regular languages are closed under complement (i.e Complement of regular language will also be regular).

## leave a comment

## 0 Comments