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.

The productions of G₁, G₂, G₃ and G₄ should be given in separate text files using the UTF-8 character encoding. The text in each such file has to match the following context-free grammar: ({Grammar, Prods, Prod, TNs, TN, N, T}, DT ∪ TT ∪ NT, P, Grammar), where DT = {’\n’, ’|’, ’→’, ’ε’}, TT = {’+’, ’-’, ’1’}, and P includes exactly

  Grammar → N ’→’ Prods ’\n’ Grammar | ’\n’ | ε,
  Prods → Prod ’|’ Prods | Prod,
  Prod → TN TNs | ’ε’,
  TNs → TN TNs | ε,
  TN → T | N,

as well as

  {T → t | t ∈ TT} and
  {N → n | n ∈ NT}.

You get to choose the set of terminals NT, as long as it is disjoint with DT ∪ TT and each terminal is exactly one Unicode code point (≈ character).

In the grammar above, note the difference between the code point ’ε’ and the notation ε for the empty string, as well as the difference between ’|’ and |, and ’→’ and →.

• Grammar: All the productions in the grammar, separated by newline characters. Optionally one can put a newline character at the end.
• Prods: The right-hand sides of one or more productions for a given nonterminal, separated by |.
• Prod: The right-hand side of a single production.
• TNs: A list of terminals and nonterminals.
• TN: A terminal or nonterminal.
• T: A terminal (+, - or 1).
• N: A nonterminal.

As an example, the productions of G could be given in the following way (with NT = {’E’, ’O’, ’N’}):

E→EOE|N
O→+|-|ε
N→1|1N

(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).