Quiz 10

The exercises below use G and G′:

• G is the context-free grammar ({E}, {+, x}, P, E), where P contains the following productions: E → E + E ∣ x.

• G′ is a function from finite sets of productions (using the non-terminals {E, T} and terminals {+, x}) to grammars defined by G′(P) = ({E, T}, {+, x}, P, E).

1. (1p) Which of the following properties, if any, does G satisfy?

   1. It is ambiguous.

   2. The language L(G) is empty.

   3. The language L(G) is infinite.

   4. The string ε ∈ L(G).

   5. The string x x ∈ L(G).

   6. The string x + x ∈ L(G).

2. (1p) How many parse trees for G, with E as the root label and yield x + x + x, are there?

3. (1p) How many left-most derivations for G, starting with E, are there of the string x + x + x?

4. (1p) For which of the following definitions of P′ is L(G′(P′)) = L(G)?

   1.   E → T + E ∣ x
        T → x

   2.   E → T + E ∣ T
        T → x

   3.   E → T + E ∣ T
        T → T + E ∣ x

   4.   E → x + E ∣ x
      

5. (1p) For which of the following definitions of P′ is G′(P′) unambiguous?

   1.   E → T + E ∣ x
        T → x

   2.   E → T + E ∣ T
        T → x

   3.   E → T + E ∣ T
        T → T + E ∣ x

   4.   E → x + E ∣ x