From a tool to a recipe
In the previous guide you met the pumping lemma for context-free languages, and you saw where it comes from: take any sufficiently long string in a context-free language, look at its parse tree, and because the grammar has only finitely many variables, some variable must repeat on one long root-to-leaf path. That repeated variable is a loop you can run again (pump up) or skip (pump down). The honest payoff is a guarantee about two pumped pieces at once. This guide is not new theory; it is the craft of wielding that guarantee to prove a target language is not context-free.
Recall the precise statement so the recipe has something to lean on. If L is context-free, there is a constant p (the pumping length) such that every string s in L with length at least p can be split into five parts, s = u v x y z, satisfying three conditions: (1) the two pumped pieces are not both empty, written |v y| at least 1; (2) the middle bundle stays short, |v x y| at most p; and (3) for every i greater than or equal to 0, the pumped string u v^i x y^i z is also in L. The single most important difference from the regular pumping lemma is that both v and y get pumped the same number of times — two windows opening in lockstep, not one.
The proof as a game against an adversary
The cleanest way to run a non-context-free proof is to picture it as a two-player game, exactly as you did for regular languages — just with more moving pieces. You are trying to show L is not context-free; an adversary insists it is. The quantifiers in the lemma decide who picks what. Whatever the lemma says 'there exists', the adversary chooses (to make your life hard); whatever it says 'for all', you choose (to expose the contradiction). Win one play of the game and you have proved L is not context-free.
- The adversary names a pumping length p (some positive integer). You do not get to see its value, so your argument must work for every p.
- You pick one specific string s in L whose length is at least p — and you pick it cleverly, so that no matter how it is later carved up, pumping must break it. This choice is the whole art of the proof.
- The adversary splits your s as u v x y z, obeying |v y| at least 1 and |v x y| at most p, but otherwise as adversarially as it likes.
- You pick a pump count i and show the pumped string u v^i x y^i z is NOT in L. Usually i = 2 (pump up) or i = 0 (pump down) is enough. Since this contradicts condition (3), L cannot have been context-free.
The single trick that makes step 4 tractable is condition (2): |v x y| at most p. That short-window guarantee means the pumped material v and y together span a stretch of length at most p, so they cannot reach across the whole string. If you build s out of three or more long, equal-length blocks, the window v x y is too narrow to touch all of them at once — and that is the wedge you drive in. This is the same pigeonhole principle in disguise that powered the lemma's proof: too little room, too many things to cover.
The classic: a^n b^n c^n is not context-free
The headline counterexample of this rung is a^n b^n c^n = { a^n b^n c^n : n at least 0 } — equal runs of a's, then b's, then c's. Two matchings have to hold at once (a's = b's and b's = c's), and that is one constraint too many for a single stack to track. Let us play the game. The adversary gives p; you choose s = a^p b^p c^p, which has length 3p, comfortably at least p, and is in L. Now the adversary must split it as u v x y z with the window v x y of length at most p.
Here is the kill. Because the window v x y has length at most p, it cannot stretch from the a-block all the way into the c-block — there are p b's wedged in between, so v and y together can touch at most two of the three letters. Whatever the adversary does, some letter is left entirely untouched by both pumped pieces. Pump up to i = 2: the touched letters increase in count while the untouched one stays fixed, so the three counts can no longer be equal, and u v^2 x y^2 z falls out of L. Contradiction. So a^n b^n c^n is not context-free.
s = a a a ... a b b b ... b c c c ... c (p of each, length 3p)
\---- p ----/ \---- p ----/ \---- p ----/
The window v x y has length <= p, so it fits inside AT MOST
two neighbouring blocks -- it can never span a...c:
case A: v x y lies in the a's (and/or b's) -> c-count never changes
case B: v x y lies in the b's (and/or c's) -> a-count never changes
(it can never reach both an a and a c: the p b's block the way)
Pump i = 2: some letters grow, the untouched letter does not
=> counts no longer all equal => NOT in L. Contradiction.Notice the contrast with the previous rung. a^n b^n IS context-free — one stack can push for the a's and pop for the b's. But a^n b^n c^n needs to verify two independent counts, and a stack discharged on the b's has nothing left to check the c's against. That single extra constraint is exactly the jump from context-free up to needing a stronger machine (a pushdown automaton, with its one stack of plates, is not enough; you would want a Turing machine).
Two power moves: intersection with a regular language
Sometimes pumping a raw target language is fiddly, but a closure fact from guide 1 of this rung gives a cleaner route. Context-free languages are not closed under intersection — the intersection of two CFLs can fail to be context-free — yet they ARE closed under intersection with a regular language. That asymmetry is a weapon. If L were context-free, then L intersected with any regular language R would still be context-free. So if you can pick an R that filters L down to a language you already know is not context-free (like a^n b^n c^n), you reach a contradiction without pumping L directly.
A worked example: let L = { w : w has equal numbers of a's, b's, and c's }. Pumping this directly is awkward because the letters can be shuffled in any order. Instead intersect with the regular language R = a* b* c* (a regex says letters appear in that order). Then L intersect R is exactly { a^n b^n c^n }, which we just proved is not context-free. If L were context-free, L intersect R would be too — contradiction. Hence L is not context-free. We borrowed a known non-CFL through the regular filter.
When pumping is too weak: Ogden's lemma
The ordinary pumping lemma is necessary but not sufficient, and worse, it is sometimes too blunt even to refute a genuine non-CFL. The trouble is that the adversary, free to place v x y anywhere short, can sometimes hide the pump inside a harmless padding region where pumping it does no damage. For such languages the basic lemma cannot force a contradiction at all — even though the language really is not context-free.
Ogden's lemma is the sharper tool that fixes this. Before the split, you get to mark at least p positions in s as 'distinguished' (think of them as highlighted letters). The lemma then guarantees the pump can be aimed at the marks: among the five parts, the window v x y contains at most p marked positions, and crucially v and y together contain at least one marked position. By choosing which letters to highlight, you steer the adversary's pump onto exactly the region where pumping must break the string — taking away its hiding place. The plain pumping lemma is just Ogden's lemma with every position marked.
A flavour of where it bites: the language { a^i b^j c^k : i, j, k at least 0 and (i = 0 or j = k) } is not context-free, yet the ordinary pumping lemma cannot prove it, because the adversary can always retreat into the i = 0 branch and pump there harmlessly. Mark the b's and c's with Ogden's lemma and the pump is forced into the j-versus-k matching, where unbalancing it produces a string outside the language. The mechanism — a repeated variable on a long root-to-leaf parse-tree path — is identical; Ogden's lemma only counts marked leaves, giving you the steering wheel.
Pitfalls, and where this leaves you
Three honest cautions before you set out. First, the lemma only refutes — passing it confirms nothing, so never write 'this string pumps, so the language is context-free.' Second, you choose the string s but the adversary chooses the split; if your proof secretly assumes a convenient split (say, 'v is all a's'), it is broken — you must defeat every legal split. Third, length matters: s must have length at least p, and your argument must hold for an unknown p, so you write s in terms of p (like a^p b^p c^p), never a fixed number.
Step back and place this on the map. You can now prove a language sits outside the context-free class — the analogue, one floor up, of proving non-regularity with the regular pumping lemma. The recipe is the same shape (adversary game), the engine is the same idea (pigeonhole forcing a repeat), and the closure toolkit gives you a slicker shortcut whenever a regular filter exposes a known non-CFL. Where ordinary pumping is too blunt, Ogden's lemma lets you aim.
And here is the encouraging flip side, the subject of the next two guides. Even though we cannot recognise every limit of context-free languages, the questions we can answer about a given grammar are remarkably tame: 'is this string in the language?' and 'does this grammar generate anything at all?' are both decidable — membership by the CYK algorithm in O(n^3) time, emptiness by a simple reachability check. The hard questions (is one grammar equivalent to another? is a grammar ambiguous?) are already undecidable. Knowing what is impossible, as you do now, is exactly what makes the possible worth celebrating.