Mathematical Foundation of Computer Science

DHARM

EQUIVALENCE OF NFA AND DFA 193

Now we shall prove that the theorem is true for string length (n + 1), hence through
induction it is true for string length n also and finally theorem is true for any length of the
string.
For that, break the string x into a symbol ‘a’ and the substring ‘y’, i.e.,
x = y.a, where y = a 1 .a 2 .a 3 ........... an and | y | = n

then, $δN(q 0 , x) = δN(δ$N(q 0 , y), a);

= δN({p 1 , p 2 , p 3 ........... pi}, a); [Assume δ$N(q 0 , y) = {p 1 , p 2 , p 3 , ... pi}]

= k∪=

i

1 (,)pak ...(1)

Now from DFA,

δD({p 1 , p 2 , p 3 ........... pi}, a) = ∪

k=

i

1 δD,()pka ...(2)

and {p 1 , p 2 , p 3 ........... pi} ← $δD(q 0 , y);

Thus, $δD(q 0 , x) = δD(δ$D(q 0 , y), a);

= δ$D({p 1 , p 2 , p 3 ...........pi}, a);

$δD(q 0 , x) = k∪=

i

1 δN(,)pak ...(3)

Compare the equations (1) and (3), we obtain,

(^) δ$N(q 0 , x) = δ$D(q 0 , x);
Which contains at least one state is in FN, i.e., FN ⊆ FD ⊆ Q. Hence, theorem is true for
string length (n + 1). Therefore, theorem is true for string length n also and finally theorem is
true for any length of the string.
Thus, proof of the theorem ends with the conclusion that language of a NFA can also be
the language of some DFA. So, if nondeterminism behavior from a NFA is removed then it
behaves like a DFA.

8.2 Method of Conversion from NFA to DFA......................................................................

Consider an example of NFA N where N is given as,
N = ({q 0 , q 1 , q 2 , q 3 }, {0, 1}, δ, q 0 , {q 3 })
where δ’s are shown in the following transition table (TT) (Fig. 8.1).

States

Input symbols

0

{q 0 ,q

q

q

1

3

3

}

{}

{}

F

{}

{}

{}

{}

q

q

q

q

0

1

2

3

1

{}

{

{}

q

q

q

0

2

3

}

F

Fig. 8.1 TTNFA.

Then construct an equivalent DFA D i.e., D = (QD, Σ, δD, q 0 , FD) for the given NFA.