1.  (10 points).   Find a context-free grammar for the following language where i,j,k ≥ 0: L = {ai bj ck  | i + j = k }

2.  (10 points).    Give an informal algorithm that, for any given context-free grammar G, can determine whether or not ϵ ∈ L(G).

3.  (10 points).   Use the CYK method to determine if aaabb is in the language of the following grammar.

S → AB

A → AA | AB | a

B → CC

C → b

4.  (10 points).    Construct a PDA M that accepts the following language over the alphabet

Σ = {a, b}

L = {w ∈ Σ*  | #a (w) ≤ #b (w) ≤ 2#a (w)}

where #a (w) is the number of a’s in w and #b (w) is the number of b’s in w .  Hint:  Take advantage of nondeterminism.

5.  (10 points).   Give the successive configurations (instantaneous descriptions) in any accepting computation for the PDA in the previous question on the input abb starting with the initial configuration.