Practice Questions (Lectures)

Question 1

Prove that the language
L = {ww: w ∈ {a, b}∗}
is not CF

Answer 1

• We know that L1 =
  {a^ib^ja^ib^j: i, j ≥ 0} is not CF
• Assume L is CF
• Then by closure theorem 2, language
  L ∩ a∗b∗a∗b∗ is CF
• But, language {ww: w ∈ {a, b∗} ∩ abab = {a^ib^ja^ib^j: i, j ≥ 0} is not CF (Thm 4), giving CONTRADICTION

Question 2

L = {w ∈ {a, b}∗ : w has the same number of a’s and b’s}
is context- free

Answer 2

Yes, proved by constructing a PDA and applying the Main Theorem

Question 3

L = {w ∈ {a, b, c}∗: w has the same number of a’s, b’s and c’s}

L = {a^pb^n: p ∈ Prime, n > p}

are not context-free

Answer 3

Yes, proved by PL

Question 4

Prove that L =
{a^mb^n: m ≥ n}
is CF

Answer 4

Construct a grammar G such that
L(G) = {a^mb^n: m≥n}
as follows:

G = (V, Σ, R, S)
where
V = {a, b, S}, Σ = {a, b}
R = {S → aS|aSb|e}

Derivation examples
S ⇒ aS ⇒ aaS ⇒ aaaSb ⇒ aaab

S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb