Q1: Closure Properties
For all integers 𝑝, 𝑞 and 𝑟, the language
{𝑎𝑛𝑏
𝑚 ∣ 𝑛, 𝑚 ≥ 0, 𝑛𝑝 + 𝑚𝑞 = 𝑟}
5
is context-free. Using this fact and the closure properties of context-free languages, prove that
𝐿 = {𝑎𝑛𝑏
𝑚 ∣ 𝑛, 𝑚 ≥ 0}
is also context-free. In your proof, do not use any languages other than these
or those derived from these using closure properties. (Proofs violating this
requirement will receive 0 marks.)
Q2 Pumping Lemma for Regular Languages
Using the pumping lemma for regular languages, prove that
𝐿 = {𝑎𝑛𝑏
𝑚𝑐
𝑘
∣ 𝑛, 𝑚, 𝑘 ≥ 0, 𝑛𝑚 = 2𝑘}
is not regular.
Q3 Pumping Lemma for Context-Free Languages
Let Σ = {𝑎, 𝑏} and
𝐿 = {𝑤 ∈ Σ∗
∣ for all nonempty 𝑠 ∈ Σ∗
, the string 𝑠𝑠𝑠 does not occur in 𝑤}.
The language 𝐿 is infinite. Using this fact and the pumping lemma for contextfree languages, prove that 𝐿 is not context-free.