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.