## 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