Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 259

Let regular language is defined over set of symbols Σ, then complement of L returns all
possible strings formed over Σ excluded the strings of the set L.

i.e. L = Σ– L ;
Now we see that how L is also a regular language.
We know that a language is regular if it is accepted by some DFA. If we construct a DFA
that accept complement of language L, then we say it is also regular.
Let M be a DFA accepting L define as,
M = (Q, Σ, δ, q 0 , F) and L = L(M)
Now if we construct a new DFA M′ by using the information of DFA M such that, the set
of final states in M′ is F′ which is given as,
F′ = Q – F
Then DFA M′ = (Q, Σ, δ, q 0 , Q – F) accepts complement of the language L.
Example 10.4. A DFA M is shown in Fig. 10.4, that accepts that language given by the regular
expression
( 1 + 0. 1 . 0 ) ( 0 + 1 )*

A

B

C

1

0

1

0, 1

0

Fig. 10.4. (M)

Now we construct the DFA M′ that accepts the complement of language L.

Sol. In the complemented DFA M′ all non final states will be final states and final state will be

nonfinal state, i.e. we obtain the DFA M′ show in Fig. 10.5.

A

B

C

1

0

1

M¢

0, 1

0

Fig. 10.5. (M′)
Thus, M′ accepts the language of the regular expression (∈∈∈∈∈ + 0. 1*) which is the
complement of L.