Assignment 6

Four grammar transformations, Bin, Del, Unit and Term, were discussed in a lecture. The results of the Bin and Term transformations are not always uniquely defined: there is a choice of how to name the new nonterminals that may be introduced.

Consider the context-free grammar G = ({E, O, N}, {+, −, 1}, P, E), where the set of productions P is defined in the following way:

  E → E O E | N
  O → + | − | ε
  N → 1 | 1 N

1. (1p) Construct one possible (correct) result of applying the Bin transformation to G. Denote this grammar by G₁.
2. (1p) Construct the result of applying the Del transformation to G₁. Denote this grammar by G₂.
3. (1p) Construct the result of applying the Unit transformation to G₂. Denote this grammar by G₃.
4. (1p) Construct one possible (correct) result of applying the Term transformation to G₃. Denote this grammar by G₄.
5. (2p) Construct the CYK table for G₄ and the string w = 1 + 1 1 − 1.

(4p) Prove that { int␣X;␣X␣=␣3;  | X ∈ {a, …, z}⁺}, containing strings like “int␣foo;␣foo␣=␣3;”, is not a context-free language over the alphabet {a, …, z} ∪ {0, …, 9} ∪ {=, ;, ␣}.

You may use the following lemmas:

• The pumping lemma for context-free languages.

• The language {ww | w ∈ Σ^*} over the alphabet Σ is not context-free if |Σ| ≥ 2.

• The closure properties for context-free languages covered in the lectures.

• The following closure property: If Σ is an alphabet and L ⊆ Σ^* is context-free, then, for any string w ∈ Σ^*, {v ∈ Σ^* | wv ∈ L} and {v ∈ Σ^* | vw ∈ L} are also context-free (see “Quotients of Context-Free Languages” by Ginsburg and Spanier).