CS 3350 Automata, Computability, and Formal Languages
Fall 2012 Test 2

Name: __________________________________________________________

1. Use the algorithm that we had in class to transform the following context-free grammar into Chomsky normal form: S --> AA, A --> aB, B --> bA, A --> ε, B --> ε.


























































2. Use the general algorithm to design a pushdown automaton that recognizes exactly the context-free language described in Problem 1.

































































3. For the context-free grammar described in Problem 1:





























































4. The sequence abaab is accepted by the following pushdown automaton: Use the general algorithm that we described in class (and that is described in the book) to list all the rules of the corresponding context-free grammar which are needed to deduce the sequence abaab. Draw a parse tree explaining how this sequence is derived by using these rules.






















































5. Let Na(s) denote the number of a's in a string s, Nb(s) denote the number of b's, and Nc(s) denote the number of c's. Prove that the language consisting of all the words s for which Na(s) = Nb(s) = Nc(s) (i.e., words which have exactly as many a's as b's as c's) cannot be recognized by a pushdown automaton.