Practice free →
HomeGATE CSEcomputerscienceTheory of Computation › Is the language $L = \{a^n b^n c^n \mid n \geq 0…

Is the language $L = \{a^n b^n c^n \mid n \geq 0\}$ context-free?

AYes — a simple CFG generates it
BUndecidable
CYes if we restrict $n \leq 100$
DNo — pumping lemma proves it not context-free
Answer & Solution
Correct answer: D. No — pumping lemma proves it not context-free
1. $L = \{a^n b^n c^n\}$ requires matching THREE counts. A PDA has ONE stack — it can match a-vs-b (push for each a, pop for each b), but then the stack is empty and can't enforce a matching c-count. 2. The PUMPING LEMMA FOR CFLs proves $L$ is not context-free. Sketch: for any pumping length $p$, take $s = a^p b^p c^p$. Any division $s = uvxyz$ with $|vxy| \leq p$ and $|vy| \geq 1$ can pump only ONE OR TWO of the three letters. Pumping breaks the equal-count condition. 3. This is a CONTEXT-SENSITIVE language (recognised by Linear Bounded Automata) but NOT context-free. 4. Contrast: $\{a^n b^n\}$ IS context-free (only one matching pair); $\{a^n b^n c^n\}$ is the simplest example that ISN'T. 5. Options A, C, D are wrong. _Source: Jeff Erickson, "Models of Computation", §5.11 (Pumping Lemma for CFLs, $a^n b^n c^n$ example)._
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions