Assignment 5

Consider the following language over the alphabet Σ = {a, b}: M = {aⁱb^i + j | i, j ∈ ℕ}.

1. (0p) Give an ambiguous context-free grammar G = ({S}, Σ, P, S) for M. Note that the grammar should have exactly one nonterminal, S.

   (There are no points for this exercise. In the following three exercises you are asked to prove that your answer is correct.)

2. (1p) Prove that G is ambiguous.

3. (3p) Prove ∀i, j ∈ ℕ. S ⇒^* aⁱb^i + j.

   You are allowed to make use of the following property without providing a proof for it: ∀α, α′, β, β′ ∈ {S, a, b}^*. (α ⇒^* α′ ∧ β ⇒^* β′) ⇒ (αβ ⇒^* α′β′).

4. (3p) Prove ∀w ∈ L(G, S). w ∈ M, where L(_, _) is the inductive construction introduced in the eleventh lecture under the heading of “Recursive inference”.

5. (3p) Give an unambiguous context-free grammar G′ for M.

   You are not obligated to provide a proof. However, note that (for a typical model of computation) there is no algorithm for checking whether two arbitrary context-free grammars implement the same language,¹ or whether an arbitrary context-free grammar is unambiguous. You should give enough explanation so that the person correcting your submission can easily see that your answer is correct.

The exercises above are loosely based on exercises from a previous version of this course, given by Ana Bove.