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 contextfree 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 contextfree language described in
Problem 1.
3. For the contextfree 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 uv^{i}xy^{i}z 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 contextfree 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 N_{a}(s) denote the number of a's in a string s,
N_{b}(s) denote the number of b's, and
N_{c}(s) denote the number of c's.
Prove that the language consisting of all the words s for which
N_{a}(s) = N_{b}(s) = N_{c}(s) (i.e., words
which have exactly as many a's as b's as c's)
cannot be recognized by a pushdown automaton.