Ogden's lemma
/ Ogden: OG-den /
Sometimes the plain context-free pumping lemma is too weak: the language is genuinely not context-free, but the lemma's freedom of where to put v x y lets your imaginary opponent always find a 'safe' split that stays in the language. Ogden's lemma fixes this by letting YOU plant flags. Before the split happens, you mark certain positions in the string as DISTINGUISHED, and the lemma then forces the pumpable pieces to actually USE your marked positions — taking away the opponent's escape routes.
Precisely: for a context-free language L there is a constant p such that if z is in L and you MARK at least p positions of z, then z splits as u v x y z' with three strengthened conditions: (1) v and y together contain at least one marked position (|v y| has >= 1 mark, so pumping cannot dodge into unmarked filler); (2) the window v x y contains at most p marked positions (not at most p symbols — the bound is on MARKS); and (3) for every i >= 0, u v^i x y^i z' is in L. The ordinary pumping lemma is just Ogden's lemma with ALL positions marked, so Ogden's is strictly stronger — every job the plain lemma does, Ogden's also does, plus more.
The payoff is reach. Ogden's lemma proves languages NOT context-free that the plain lemma cannot touch, and it is the standard tool for showing certain grammars are INHERENTLY ambiguous (no grammar for the language can avoid ambiguity). A famous example it handles cleanly is { a^i b^j c^k d^l : i = 0 OR j = k = l }, where you mark the b's, c's, or d's to force the pump into the part that must stay balanced. Like every pumping-style lemma, it is necessary but not sufficient — failing it proves non-context-freeness, but satisfying it proves nothing positive.
For L = { a^i b^j c^k d^l : i = 0 or j = k = l }, the plain lemma struggles because the i = 0 escape hatch always offers a safe split. Mark, say, all the b's: Ogden's lemma forces v and y to include marked b's, and pumping then breaks the j = k = l balance, exposing the contradiction the plain lemma could not.
Mark positions to force the pump where you want it — a strictly stronger tool than the plain CFL pumping lemma.
The bound in condition (2) counts MARKED positions, not all symbols — a frequent confusion. Ogden's lemma generalises the plain pumping lemma (mark everything) but, like it, is necessary not sufficient.