Assignment 4 (Due 19 Apr at end of class)

General Rules:

a. Please hand in only your own work.
b. Grades discounted 10% per day late.

Tasks

1) Supose that G is a CFG and that w is word of length l (that's the letter "l"; so the answer will be a formula that depends on "l") generated by G. How long is the derivation of w in G, if:
a) G is in CNF
b) G is in GNF?
2) Can every CFL (without epsilon) be generated by a CFG which only has productions of the form A -> BCD or A -> a (with no epsilon productions)?
Explain why or why not.
3) Find a GNF grammar equivalent to the following (CNF) CFG:
S-> AA | 0
A -> SS | 1
4) Construct a PDA which accepts the langauge generated by:
S -> aAA
A -> aS | bS | a
5) Construct a CFG which accepts:
L = { 0^n1^n | n >= 1} U { 0^n1^2n | n >=1 } (i.e. strings of (0+1)* where it starts with n zeros followed by either n or 2*n ones.)