Description
Problem 1. (30 points)
Find the language recognized by the given DFA:
1.
start s0 s1
s2
1
0
0,1
0
1
2.
start s0 s1
s2
0
1
1
0
0,1
3.
start s0 s1 s2 s3
0
1 0
1 0,1
0,1
Problem 2. (20 points)
Show that the following grammar generates the language {a
nb
nc
n | n ≥ 0}.
S ::= aST | λ
T ::= BC
CB ::= BC
aB ::= ab
bB ::= bb
bC ::= bc
cC ::= cc