Reference no: EM133096727

CPSC 313 Introduction to Computability - University of Calgary

Question 1: Let Σ = {a, b, c}. Give a context-free grammar for the language

L₁ = {aⁱbⁱ c^k | i,j,k ∈ N and i < j} ⊆ Σ*

and sketch a proof that your language is correct:

• For each variable V in the context-free grammar that you have given, describe (using set-theoretic notation) the set S_v ⊆ Σ* which includes all strings w ∈ Σ* such that V => *w.

• For each of these variables V and set S_v, prove that your answer is correct. That is, prove that, for every string ω ∈ Σ*, V => ω if and only if ω ∈ S_v. (One or more of these proofs might be almost the same as a similar proof that has been included in the lecture material. When this is the case it is acceptable to say so, and describe how the proof from the notes would be modified to prove your claim, instead of writing out the proof all over again.)

Note: N is the set of non-negative integers (so that 0 ∈ N).

Question 2. Let Σ = {a, b, c} once again. Give a context-free grammar for the language

L₂ = {aⁱbⁱc^k i, j,k ∈ N and i < k} ⊆ Σ*.

Once again, for each variable V in the context-free grammar that you have given, describe (using set-theoretic notation) the set S_v ⊆ Σ* of strings ω ∈ Σ* such that V =>* ω (It is not necessary to prove your claims, this time.)

Question 3. Once again, let Σ = {a, b, c}. Give a context-free grammar for the language

L₃ = {aⁱbⁱc^k i, j,k ∈ N and i ≠ j or i ≠ k (or both)} ⊆ Σ*.

As above, for each variable V in the context-free grammar that you have given, describe (using set-theoretic notation) the set By S_v ⊆ Σ* of strings ω ∈ Σ* such that V =>* ω. (It is not necessary to prove your claims).

Note: You should find the answers for the first two problems to be useful.