A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Context-free languages cannot recognize dependencies across three or more independently nested groups (e.g., {aⁿbⁿcⁿ}). The pumping lemma for CFLs establishes non-context-free languages. These limitations motivate even more powerful models like Turing machines.
You have seen that context-free languages, recognized by pushdown automata, are strictly more powerful than regular languages. A PDA can match balanced parentheses, count a's against b's, and parse nested structures — things no finite automaton can do. But context-free languages have their own ceiling, and understanding where they fail reveals why the Chomsky hierarchy does not stop at level 2.
The fundamental limitation of a pushdown automaton is that it has exactly one stack. A stack lets you match one pair of dependent groups: push a's, then pop while reading b's, and you have verified that {aⁿbⁿ} is balanced. But what about {aⁿbⁿcⁿ} — strings where three groups must all have the same count? A single stack can verify that the a's match the b's (push during a's, pop during b's) or that the b's match the c's (push during b's, pop during c's), but it cannot do both simultaneously. By the time you have verified the first pair, the stack evidence is gone. This is not a failure of cleverness in PDA design — it is a provable limitation of the context-free class itself.
The pumping lemma for context-free languages makes this precise. It states that for any CFL, there exists a pumping length *p* such that any string of length ≥ *p* can be divided into five parts, s = uvxyz, where |vy| ≥ 1, |vxy| ≤ *p*, and for all i ≥ 0, uvⁱxyⁱz is also in the language. The key constraint is that the two "pumped" pieces v and y can only appear in two positions — they cannot simultaneously control three independent parts of the string. To prove {aⁿbⁿcⁿ} is not context-free, you pick a string like aᵖbᵖcᵖ and show that no matter how you choose v and y within the length constraint, pumping will increase at most two of the three symbol counts, breaking the three-way equality.
These limitations are not merely theoretical curiosities. They explain why certain programming language features — like requiring that every variable is declared before use *and* used the correct number of times — cannot be checked by a context-free parser alone. They also motivate the next step in the computational hierarchy: Turing machines, which replace the stack with an unrestricted read-write tape, giving them enough memory to track arbitrarily many dependencies simultaneously. The jump from "one stack" to "unlimited tape" is what separates decidable computation from context-free parsing.