Home › GATE CSE › computerscience › Theory 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)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?