## 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:
• draw a tree that describes the derivation of the sequence abab,
• use this tree to determine the subdivision of this sequence into u, v, x, y, and z;
• for i = 0 and i = 2, draw trees explaining how the corresponding sequences uvixyiz can be derived in this grammar.

```

```
4. The sequence abaab is accepted by the following pushdown automaton:
• this automaton starts at state 0,
• when in state 0, the rule (a, ε) --> a leads to state 1,
• when in state 1, the rule (b, a) --> b leads to state 2,
• when in state 2, the rule (a, ε) --> z leads to state 2 again,
• when in state 2, the rule (a, z) --> ε leads to state 3,
• when in state 3, the rule (b, b) --> ε leads to the final state 1.
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.