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.