Q2Theory of Computation

Question

(a) State and prove the Pumping Lemma for Context-Free Languages. (b) Use Pumping Lemma to show that L = {a^n b^n c^n | n ≥ 1} is not context-free.

Answer 1

Pumping Lemma for CFL: $s = uv w x y$ , $∣ v w x ∣ \leq p$ , $∣ v x ∣ > 0$ , $u v^{i} w x^{i} y \in L$ . For $a^{n} b^{n} c^{n}$ , pumping $v, x$ will imbalance the counts of a, b, or c, showing it's not a CFL.

Q2Theory of Computation

Question

Answer