Mathematical Foundation of Computer Science

DHARM

EQUIVALENCE OF NFA AND DFA 209

(iii) State 0 Î 1

q 0

q 1

q 2

q 3

{}q 2

{}q 1 {}q 0

{}q2ss

FFF

{}q 3

{}q 1

{}q 2

(c)

{}q 3

{}q 0

Fig 8.15

8.2 Construct the equivalent DFA’s from the given NFA’s whose transition tables are shown in

Fig. 8.16.

(i) State 02

q 0

q 1

q 2

F

{}q 1

{}q 1

{}qq 01 , F

F

{}q 2

(a)

1

{}qq 01 ,

{}qq 12 ,

(ii) State 02

q 0

q 1

q 2

q 3

{}qq 12 ,

{}q 3

{}qq,q 013 ,

FF

F

F

{}q 1

{}q 3

(b)

1

{}qq 01 , F

{}q 2

(iii)

State^0

q 0

q 1

q 2

q 3

{}qq 12 ,

{}q 1

F {}q 3

(c)

1

{}qq 01 , {}q 3

F

{}q 2

Fig 8.16

8.3 Construct the equivalent DFA for all the given NFA’s with ∈ moves in exercise 8.1.