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.