Ogden's lemma states that if a language is context-free, then there exists some number (where may or may not be a pumping length) such that for any string of length at least in and every way of "marking" or more of the positions in , can be written as
with strings and , such that
has at most marked positions,
has at least one marked position, and
for all .
In the special case where every position is marked, Ogden's lemma is equivalent to the pumping lemma for context-free languages. Ogden's lemma can be used to show that certain languages are not context-free in cases where the pumping lemma is not sufficient. An example is the language .
Ogden's lemma can also be used to prove the inherent ambiguity of some languages.
Each category of languages, except those marked by a *, is a proper subset of the category directly above it.Any language in each category is generated by a grammar and by an automaton in the category in the same line.