4/22/09 (due 4/29/09)
The following problems are all taken from the handout on Finite Automata
from Rosen's book. Note that you're not repsonsible for regular
grammars (which are discussed in Section 12.4).
Section Number Points Comments
12.3 8(a),(b),(c),(d) 12 If the statement is true, prove it; if not, provide a
countexample. Grading: (a) - 2 points; (b) - 3 points; (c) - 2
points; (d) - 5 points. (The scoring should be viewed as a hint
as to the expected length of the answer.)
12 4
14 4 Define xn+1 inductively as xx^n, and use induction.
16 3
18 3
20 3
23 4
25 4
39 2
41 2
45 3
47 3
52 3
54 3
12.4 3(a),(c),(d) 3
7(a),(b),(d) 6
23 4 You don't have to prove the pumping lemma; just use it.
24 4