Problem Solving in Automata, Languages, and Complexity

48 FINITE AUTOMATA

Solzstion. Following the above procedure, we obtain the following table for the
transition function S’ of the DFA:

s /

QE = IPI

Qo = {P> d

Qol = {P, r)

The DFA is thus

M’= ({{P}t{P,q},{P,r}},{o,l},s’,{P},{iP,q},{P,r)))* n

From the above construction, we see that for each NFA there exists a DFA
accepting the same language accepted by the NFA. Moreover, a DFA is also
an NFA. Therefore, we have the following theorem.

Theorem 2.25 A language is accepted by an NFA if and only if it is accepted
by a DFA.

Theorem 2.25 provides us with an easy tool to construct a DFA for a given
language L: we can first construct an NFA for L and then convert it to a
DFA. The following are some examples.

Example 2.26 Let M = ({p,q, r, s}, {0,1},6,p, {q,s}) be an NIM given by

s 0 1

P {a,sl (a)

I

4 w {!I, f-1

r is) {PI

s - iPI

Construct an NFA that accepts L(M).

Solution. It is hard to figure out the construction of such an NFA ALP directly
from M. In particular, the naive approach of changing nonfinal states of 44
to final states and changing final states of A4 to nonfinal states does not work.
This is due to the nature of nondeterminism of the NFA’s: It is possible that,
for some string X, Qxn F # 8 and Qzn (Q- F) # 8; then, x would be accepted
by both M and the new NFA M’. (For instance, here we have Qol = {p, q, r}
and F = {q,s}, and so the string 01 would be accepted by both M and M’.)
Therefore, M’ does not accept L(M).
Instead, we can apply the subset construction to get the required NFA as
follows: We first find a DFA MD equivalent to M and, then, change final
states of MD to nonfinal states and nonfinal states of MD to final states to
get a new automaton M’. The new automaton we get is actually a DFA.