Lecture quiz answers

Nils Anders Danielsson

Lectures 1-2

1, 4, 5.
2, 3, 5.
Some correct answers: (a + bc^*d)^*(ε + bc^*), a^*(ε + b(c + da^*b)^*(ε + da^*)).
One correct answer: (ε + ab^*)^*ab^*.
2, 3.
2, 3, 5, 7.

	a	b	c
→ * A	A	A	B
B	B	A	B

	a	b
→ * A	A	A

One correct answer: G = ({S}, {0}, S → 0, S), α = SS, β = S0.
If α ⇒ β, then α must have the form α₁Aα₂ and β the form α₁γα₂ for some α₁, α₂, γ ∈ (N ∪ Σ)^* and A ∈ N with A → γ ∈ P.

One of the lemmas implies that γ ∈ L_N^*(G, γ), and because A → γ ∈ P one of the introduction rules for L_N can be used to show that γ ∈ L_N(G, A). By another lemma we then get γ ∈ L_N^*(G, A).

We also have α₁ ∈ L_N^*(G, α₁) and α₂ ∈ L_N^*(G, α₂). By using the last of the listed lemmas twice we get α₁γα₂ ∈ L_N^*(G, α₁Aα₂), i.e. β ∈ L_N^*(G, α).
2, 4.
24.
E₃ ^ E₂ | E₃.

3.
Denote the language by L. The set of context-free languages is closed under homomorphisms, so if L is context-free, then h(L) is also context-free, where h ∈ ℘({0, 1, 2, 3, 4, 5, 6}^*) → ℘({0, 1, 2}^*) is defined as a “lifting” (see the slides) of the following function:

  h ∈ {0, 1, 2, 3, 4, 5, 6} → {0, 1, 2}^*
  h(0) = ε
  h(1) = 0
  h(2) = ε
  h(3) = 1
  h(4) = ε
  h(5) = 2
  h(6) = ε

However, h(L) = {0ⁿ1ⁿ2ⁿ | n ∈ ℕ}, which is known not to be context-free. Thus L is not context-free.
2. Pick some alphabet Σ and context-free language L ⊆ Σ^* such that L̅ is not context-free. Let R be Σ^*. We have R ∖ L = Σ^* ∖ L = L̅.
One can let step(F) = {A | A → BC ∈ P, B ∈ F} and initialise F to {A | A → a ∈ P}.
N/A.