Homework #6


1.  Construct a pushdown automata for strings over {a,b} with
exactly twice as many "a"s as "b"s.


2.  Construct a PDA for the language {a^i b^j:  i neq j}


3.  Use the procedure outlined in class to generate a PDA from a CFG to
generate a PDA for the CFG G below.  Trace the operation of the PDA on the
input string (()()).

    G = ({S, (, )}, {(, )}, R, S)
    R = {S -> e,
	 S -> SS,
	 S -> (S)}

4.  Convert grammar G into an equivalent Chomsky Normal Form grammar.

    G = (V, Sigma, R, E)
    V =     {+, *, (, ), id, T, F, E}
    Sigma = {+, *, (, ), id}
    R =     {E -> E + T | T
	     T -> T * F | F
	     F -> ( E ) | id


5.  Let G be a grammar in Chomsky normal form.  If w has length n and is an
element of L(G), what is the maximum possible depth of any derivation
tree for w?  What is the minimum possible depth of any derivation tree for w?
Provide precise bounds, and prove that your answers are the best possible.
Note that the depth of a tree is the maximum number of edges on any simple path
from the root to a leaf.