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.