Quiz 12

(1p) Let the context-free grammar G be ({S}, {0, 1}, (S → 0 | 1S1), S). Which of the following languages, if any, do we get if we substitute the language {0, 1} for a, and the language L(G) for b, in the language {bub | u ∈ {a}^*}?

1. {1ⁿ01ⁿw1ⁿ01ⁿ | n ∈ ℕ, w ∈ {0, 1}}

2. {1^m01^mw1ⁿ01ⁿ | m, n ∈ ℕ, w ∈ {0, 1}}

3. {1ⁿ01ⁿw1ⁿ01ⁿ | n ∈ ℕ, w ∈ {0, 1}^*}

4. {1^m01^mw1ⁿ01ⁿ | m, n ∈ ℕ, w ∈ {0, 1}^*}

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

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

2. {uuvv | u ∈ {0}⁺, v ∈ {1}⁺} ∩ {uvvu | u ∈ {0}⁺, v ∈ {1}⁺}

3. {ssttuvvu | s, u ∈ {0}⁺, t, v ∈ {1}⁺}

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

5. {(uvvu)ⁿ | u ∈ {0}⁺, v ∈ {1}⁺, n ∈ ℕ}

6. {(ab)^mc²ⁿ(ab)^m | m, n ∈ ℕ}

7. {uvu | u ∈ {0, 1}^*, v ∈ {2, 3}^*}

(1p) Construct the CYK table for the context-free grammar ({S, A}, {0, 1}, (S → 0 | SA | AA, A → 1 | AS), S), which is in Chomsky normal form, and the string 01101. How many occurrences of the nonterminal A are there in the CYK table?

(1p) Construct the CYK table for the context-free grammar ({S, A}, {0}, (S → SS | AA, A → 0), S), which is in Chomsky normal form, and the string 00000. How many occurrences of the nonterminal S are there in the CYK table?