Ogden's lemma

In the theory of formal languages, Ogden's lemma (named after William F. Ogden)[1] is a generalization of the pumping lemma for context-free languages.

Despite Ogden's lemma being a strengthening of the pumping lemma, it is insufficient to fully characterize the class of context-free languages.

[2] This is in contrast to the Myhill-Nerode theorem, which unlike the pumping lemma for regular languages is a necessary and sufficient condition for regularity.

is generated by a context-free grammar, then there exists some

We will use underlines to indicate "marked" positions.

Ogden's lemma is often stated in the following form, which can be obtained by "forgetting about" the grammar, and concentrating on the language itself: If a language L is context-free, then there exists some number

(where p may or may not be a pumping length) such that for any string s of length at least p in L and every way of "marking" p or more of the positions in s, s can be written as with strings u, v, w, x, and y, such that 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.

The special case of Ogden's lemma is often sufficient to prove some languages are not context-free.

is a standard example of non-context-free language,[3] Suppose the language is generated by a context-free grammar, then let

be the length required in Ogden's lemma, then consider the word

Then the three conditions implied by Ogden's lemma cannot all be satisfied.

Similarly, one can prove the "copy twice" language

Ogden's lemma can be used to prove the inherent ambiguity of some languages, which is implied by the title of Ogden's paper.

be the pumping length needed for Ogden's lemma, and apply it to the sentence

By routine checking of the conditions of Ogden's lemma, we find that the derivation is

being the descendent of one node in the derivation tree.

, the two sub-sentences have nonempty intersection, and since neither contains the other, the two derivation trees are different.

is inherently ambiguous, and for any CFG of the language, letting

be the constant for Ogden's lemma, we find that

has an unbounded degree of inherent ambiguity.

The proof can be extended to show that deciding whether a CFG is inherently ambiguous is undecidable, by reduction to the Post correspondence problem.

It can also show that deciding whether a CFG has an unbounded degree of inherent ambiguity is undecidable.

(page 4 of Ogden's paper) Given any Post correspondence problem over binary strings, we reduce it to a decision problem over a CFG.

is inherently ambiguous iff the Post correspondence problem has a solution.

has an unbounded degree of inherent ambiguity iff the Post correspondence problem has a solution.

Bader and Moura have generalized the lemma[4] to allow marking some positions that are not to be included in vx.

Their dependence of the parameters was later improved by Dömösi and Kudlek.

[5] If we denote the number of such excluded positions by e, then the number d of marked positions of which we want to include some in vx must satisfy

The statement becomes that every s can be written as with strings u, v, w, x, and y, such that Moreover, either each of u,v,w has a marked position, or each of