C.
1, 4, 6.
2.
2, 4, 6.
2, 3.
2, 4.
1, 3.
4.
Injective: f, g. Surjective: g, h.
2, 3.
1.
N/A.
1, 3.
1.
N/A.
2.
2. This property holds by definition, the other one doesn’t.
1, 5.
3, 5.
Proof sketches:
Counterexample: L = {ε}, n = 1.
Counterexample: L = {0}, M = {1}.
L(M ∪ N) = { uv | u ∈ L, v ∈ M ∪ N } = { uv | u ∈ L, v ∈ M } ∪ { uv | u ∈ L, v ∈ N } = LM ∪ LN.
Counterexample: L = {ε, 1}, M = {1}, N = {ε}.
We can prove a stronger property: L*L* = { uv | u ∈ L*, v ∈ L* } = { uv | u ∈ ⋃n ∈ ℕ Ln, v ∈ ⋃n ∈ ℕ Ln } = { uv | m, n ∈ ℕ, u ∈ Lm, v ∈ Ln } = { u | m, n ∈ ℕ, u ∈ Lm + n } = { u | n ∈ ℕ, u ∈ Ln } = { u | u ∈ ⋃n ∈ ℕ Ln } = L*.
2, 5.
4.
1, 4, 6.
1, 3, 4, 5.
2, 3, 5, 6.
4.
3, 4, 6.
1, 4.
Proof sketches:
1: δhat(q, a) = ⋃r ∈ δ(q, a)δhat(r, ε) = ⋃r ∈ δ(q, a){r} = δ(q, a).
4: Proof by induction on the structure of u:
⋃r ∈ δhat(q, ε)δhat(r, v) = ⋃r ∈ {q}δhat(r, v) = δhat(q, v) = δhat(q, εv).
⋃r ∈ δhat(q, au)δhat(r, v) = ⋃r ∈ ⋃r′ ∈ δ(q, a)δhat(r′, u)δhat(r, v) = ⋃r′ ∈ δ(q, a)⋃r ∈ δhat(r′, u)δhat(r, v) = ⋃r ∈ δ(q, a)δhat(r, uv) = δhat(q, auv).
1024.
10.
N/A.
1, 2, 3.
3, 4, 6.
1, 2.
5.
3.
1, 4, 5.
2, 3, 5.
1, 3, 5, 6, 7.
Some correct answers: (a + bc*d)*(ε + bc*), a*(ε + b(c + da*b)*(ε + da*)).
Some correct answers: (ε + ab*)*ab*, (ab*)+.
4.
1, 3, 4.
1, 2, 3, 4.
1, 2.
3, 4.
1, 2, 4.
3.
No.
| a | b | c | |
|---|---|---|---|
| → * [s₀] | [s₀] | [s₀] | [s₁] |
| [s₁] | [s₀] | [s₂] | [s₁] |
| [s₂] | [s₁] | [s₀] | [s₁] |
3.
2, 4.
One correct answer: ε ∣ 000S11.
2, 5.
2, 3.
1, 2, 4, 5.
The yield of a parse tree with A in the root is in the language corresponding to A.
The yield of a list of terminals and parse trees with α as the terminals/root nonterminals is in the language corresponding to α.
No, because L(G, A) ⊆ Σ*. Counterexample: A = S, α = S, G arbitrary (with S as its start symbol).
LN was defined in order to make this property true: a list of nonterminals and terminals can be derived from A if and only if it is in LN(G, A).
The language corresponding to αβ is the concatenation of the language corresponding to α and the language corresponding to β.
No, because the string generated by αβ can, in general, be split up in several different ways. Counterexample: u = 01, v = ε, α = 0, β = 1, G arbitrary except that its set of terminals contains 0 and 1.
There are two cases to consider:
ε: We have ε ∈ L(G, S) because there is a production S → ε and ε ∈ LL(G, ε).
0w1: The inductive hypothesis tells us that w ∈ L(G, S). It is now straightforward to construct a derivation tree for 0w1 ∈ L(G, S).
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 γ ∈ LNL(G, γ), and because A → γ ∈ P one of the introduction rules for LN can be used to show that γ ∈ LN(G, A). By another lemma we then get γ ∈ LNL(G, A).
We also have α₁ ∈ LNL(G, α₁) and α₂ ∈ LNL(G, α₂). By using the last of the listed lemmas twice we get α₁γα₂ ∈ LNL(G, α₁Aα₂), i.e. β ∈ LNL(G, α).
2, 4.
For 2: S ⇒lm ε and S ⇒lm S ⇒lm ε.
For 4: S ⇒lm 1A1 ⇒lm 1S1 ⇒lm 11 and S ⇒lm 1S1 ⇒lm 11.
3.
E₃ ^ E₂ | E₃.
N/A.
|℘({1, 2, …, 10})| + 1 = 210 + 1 = 1025.
({S, A, B}, ∅, (S → AB, A → ε), S).
G is ambiguous, the transformed grammar is not.
1.
3: F({01}*) = F(⋃n ∈ ℕ {01}n) = F(⋃n ∈ ℕ {(01)n}) = F({(01)n | n ∈ ℕ}) = ⋃n ∈ ℕ F((01)n) = ⋃n ∈ ℕ (F(0)F(1))n = (F(0)F(1))* = ({a}{b, c})* = {ab, ac}*.
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) = {0n1n2n | n ∈ ℕ}, which is known not to be context-free. Thus L is not context-free.
3: Pick some alphabet Σ and context-free language L ⊆ Σ* such that L̅ is not context-free. Let R be Σ*, which is a regular language. We have R ∖ L = Σ* ∖ L = L̅.
{0, 1, A, S}.
N/A.
3, 4.
3, 4.
2.
1, 2, 4, 6.
1, 3, 5, 6.