Quiz 11

Let the context-free grammar G be ({S, A, B, C, D, E, F}, {0, 1, 2}, P, S), where the set of productions P is defined in the following way:

  S → S | ABC
  A → ε | D
  B → C1C
  C → 0
  D → AA | AB
  E → BA
  F → F

1. (1p) Which of the following statements, if any, are correct for the grammar G?

   1. The nonterminal S is generating.

   2. The nonterminal F is reachable.

   3. The terminal 2 is useful.

   4. The nonterminal S is nullable.

   5. The nonterminal D is nullable.

   6. The pair (A, D) is a unit pair.

   7. The pair (B, B) is a unit pair.

   8. The pair (S, C) is a unit pair.

2. (2p) Which of the following context-free grammars, if any, are in Chomsky normal form, do not contain useless symbols, and generate the same language as the grammar G?

   Some hints: Use the procedure in the course text book to turn G into a grammar in Chomsky normal form. Simplify the grammars that are in Chomsky normal form, so that it is easier to see what languages they define.

   1. ({S, A, B, C, D, E, F}, {0, 1, 2}, P, S), where the set of productions P is defined in the following way:

        S → AE | BC
        A → AA | AB | CF
        B → CF
        C → 0
        D → 1
        E → BC
        F → DC

   2. ({S, A, B, C, D, E, F}, {0, 1}, P, S), where the set of productions P is defined in the following way:

        S → AE | BC
        A → AA | AB | CF
        B → CF
        C → 0
        D → 1
        E → BC
        F → DC

   3. ({S, A}, {0, 1}, P, S), where the set of productions P is defined in the following way:

        S → A0100 | 0100
        A → AA | A010 | 010

   4. ({S, A, B, C, D, Z, O}, {0, 1}, P, S), where the set of productions P is defined in the following way:

        S → AB | CZ
        A → AA | AC | ZD
        B → CZ
        C → ZD
        D → OZ
        Z → 0
        O → 1

   5. ({S, A, B, C, D, E, Z, O}, {0, 1}, P, S), where the set of productions P is defined in the following way:

        S → AB | CZ
        A → AA | AC | ZD
        B → CZ
        C → ZD
        D → OZ | ED
        E → EE
        Z → 0
        O → 1

3. (1p) Consider the language L defined by the context-free grammar ({S}, {0, 1}, S → 0S1 | ε, S). According to the pumping lemma for context-free languages there is some m ∈ ℕ such that P(m) holds, where P(m) is the property ∀w ∈ L. |w| ≥ m ⇒ ∃r, s, t, u, v ∈ {0, 1}^*. w = rstuv ∧ su ≠ ε ∧ |stu| ≤ m ∧ ∀n ∈ ℕ. rsⁿtuⁿv ∈ L. What is the smallest m ∈ ℕ for which P(m) holds?

4. (1p) Which of the following languages, if any, are context-free?

   1. {w ∈ {0, 1}^* | (|w| = 5 ∧ ∄u, v ∈ {0, 1}^*. w = u00v) ∨ |w| = 3}

   2. {uvuv | u ∈ {0}⁺, v ∈ {1}⁺}

   3. {uuvv | u ∈ {0}⁺, v ∈ {1}⁺}

   4. {uvvu | u ∈ {0}⁺, v ∈ {1}⁺}