(a)
(b)
(c)
21. Obtain the NDA with state table shown below.
f
Input
State
0
1
s 0
s 0 , s 1
s 3
s 1
s 0
s 1 , s 3
s 2
s 0 , s 2
s 3
s 0 , s 1 , s 2
s 1
22. Determine the state table for the NDA with state diagram as shown
below.
23. Determine a DFA that recognizes the same language as the NDA shown
in problem 2.2 (Determine the language first).
24. Determine the language recognized by the NDA shown below.
104
Theory of Automata, Formal Languages and Computation
s 3
s 1
s 2
s 4
s 0
Start
0
0,1
1
1
0
0
s 0
s 1
Start
1
0,1
s 0
s 1
Start
s 2
s 3
0
1
0,1
1
0
0,1
s 0
s 1
Start
s 2
s 3
1
1
0
0,1
0
0,1