Mathematical Foundation of Computer Science

DHARM

208 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

1

ABCD

0

BD

CD

F D

ABD

0

0

1

0

1

(^10)
1, 0
1
Fig. 8.14
Note. The nature of the state Φ is such that, when automan reaches to this state then it will
disappear or it never returns back.

EXERCISES

8.1 Construct the equivalent NFA from the shown transition tables (Fig. 8.15) given for NFA with

∈-moves.

(i) State 0 Î 1

q 0

q 1

q 2

q 3

F

{}qq 12 ,

{}q 1 {}q 2

{}qq 01 ,

FF

FF

{}q 2

{}q 3

{}q 3

(a)

(ii)

State 0 Î 1

q 0

q 1

q 2

q 3

F

{}qq 12 ,

{}q 1

{}qq 01 ,

FF

F

F

{}q 3

{}q 1

{}q 3

(b)

q 4 {}q 3 F {}q 4

F