13. Obtain a grammar in Chomsky Normal Form equivalent to
S
aAbB A aA a B
bB b
→
→
→
,
| ,
| .
14. Convert the following NFA to DFA.
15. Prove that for every NFA there is an equivalent NFA that has only one
final state.
16. Given M
q q
q q
= ({ , }, { , }, , , { })
0
1
0
1
01 ∆
is an NFA with
∆ = {( , , ), ( , , ), ( , , ), ( , , ), ( , ,
q
q
q
q
q q
q q
q q
0
0
0
1
0
1
1
0
1
0
0
1
1
1 1 )}
Draw the state transition diagram for M. Convert to a DFA using subset
construction.
17. Show that the grammar with productions S
aSb SS
→
| | λ, is ambiguous.
18. Show that the grammar
S
aSbS bSaS
→
|
| λ
is ambiguous.
19. Give the derivation tree for (((
) * ))
,
a b c
a b
+
+ + using the grammar
G V T E P
V
E T F I
E
T
T
F
F
I
E
E T
T
T F
F
E
I
a
=
=
→
→
→
→ +
→
→
→
( , , , )
{ , , , }
*
( ),
| |
b c
20. Eliminate useless productions from
S
a aA B C
A aB
B
Aa
C
cCD
D ddd
→
→
→
→
→
| | |
|
,
λ
21. Show that the two grammars
S
abAaA abAbb ba
A aaa
→
→
|
| ,
152
Theory of Automata, Formal Languages and Computation
q 0
q 4
q 3
q 5
λ
λ
λ
a
aba