1. (a) Using the state partitioning algorithm presented in class, find the minimal automaton equivalent to the following: start q0 q1 q2 q3 q4 q5 0 1 0 1 1 0 0; 1 0; 1 0; 1 (b) What is the language recognized by this automaton (Σ = f0; 1g)? 2. Prove the each of the following languages are not regular. You may use the pumping lemma, or closure properties of the regular langauges. (a) f0n1m0n j m; n ≥ 0g (b) f0m1n j m 6= ng (c) fwtw j w; t 2 f0; 1g∗g (HINT: One way to do this is to use closure under intersection to get a simpler pumping lemma proof.) 3. Give CFGs for the following languages over σ = f0; 1g (a) fw j w = wRg (b) fw j w contains the same number of 0’s and 1’sg (c) fw j w = 0n1n; n ≥ 0g 4. Give a CFG that generates the language A = faibjck j i = j or j = k where i; j; k ≥ 0g Is your grammar ambiguous. Why or why not? 5. Convert the following grammar into a grammar in Chomsky normal form: E ! E + T j T T ! T ∗ F j F F ! (E) j num 6. Using the CNF version of the grammar E ! E ∗ E j E + E j (E) j id j num given in class, show the result of running the CYK algorithm on the string w = (id + num) ∗ num. Just show the entries of the resutling table. 7. Is every grammar in CNF unambiguous? If your answer is "yes", provide a proof. If your answer is "no", provide a counterexample. 1
