Problem Solving in Automata, Languages, and Complexity

2.4 Converting an NFA to a DFA 49

Qc = {P)

Qo = GLS)

QI = {q}

Qoo = { 1 r

QOI = {P,w)

QII = (Q,r)

Qooo = {s}

Qolo = is r, 4

QIIO = {r, s}

Qoooo =^0

Figure 2.30: The transition function of &!D in Example 2.26.

For the first step, we obtain ~VD = (QD, (0, 1},6~, {p}, FD), where the set
QD and the transition function SD are as shown in Figure 2.30, and the set
of final states is

Now, the DFA A? = (SD, (0, I}, SD, {p}, QD - FD) accepts L(M), where

QD - FD = {{PI, (4, w^0

Example 2.27 Constrzsct a DFA accepting the set of call binary strings in
which the ji’fth symbol from right is 0.

Solution. Is is easy to construct an NFA for this language: Just draw a

checker as shown in Figure 2.31(a). This checker recognizes all strings of

length 5 which begins with 0.

Now, we add two loops qo o\ qo and qo 1\ qo to the checker and this

is the required NFA ( see Figure 2.31(b)). M ore formally, this NFA can be

expressed as M = ((q0, ql, l 9 l j 45}, (0, l}, 4 qo, {q5}>, 144th

~(~o,O> = {Qo, Ql}, s(Qo,l> = {ao},

S(qi, 0) = S(qi, 1) = qi+l, for 1 < i 5 4.

qq5,q = qq5,q = 0. -

Next, we convert this NFA M to an equivalent DFA M’ = (Q’, (0, l}, 6’,

{qo}, F’), where

Q

/

= {q’ I !I’& {Qo,Q1,***,45),Qo E !I’),

F’ = {q’ E Q’ I 45 E CL