CSCI 510 Homework # 2
1. Let A/B = {w|wx ∈ A for some x ∈ B}. Show that if A is context free and B is regular then A/B is context-free. 2. For any language A, let suffix(A) = {v|uv ∈ A for some string u}. Show that the class of context-free languages is closed under the suffix operation. 3. Show that if G is a CFG in Chomsky normal form, then any string w ∈ L(G) of length n ≥ 1, exactly 2n−1 steps are required for any derivation of w. Give a proof by induction.
1
