Ogden's lemma

In the theory of formal languages, Ogden's lemma (named after William F. Ogden) 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. 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.

Statement

Template:Math theoremWe will use underlines to indicate "marked" positions.

Special cases

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 Template:Mvar is context-free, then there exists some number $p\ge 1$ (where Template:Mvar may or may not be a pumping length) such that for any string Template:Mvar of length at least Template:Mvar in Template:Mvar and every way of "marking" Template:Mvar or more of the positions in Template:Mvar, Template:Mvar can be written as

$s=uvwxy$

with strings Template:Mvar and Template:Mvar, such that

1. Template:Mvar has at least one marked position,
2. Template:Mvar has at most Template:Mvar marked positions, and
3. $u{v}^{n}w{x}^{n}y\in L$ for all $n\ge 0$.

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 $\{a^i{b}^j{c}^k{d}^l:i=0\text{ or }j=k=l\}$.

Example applications

Non-context-freeness

The special case of Ogden's lemma is often sufficient to prove some languages are not context-free. For example, $\{a^m{b}^n{c}^m{d}^n|m,n\ge 1\}$ is a standard example of non-context-free language,

Similarly, one can prove the "copy twice" language $L=\{w^2|w\in \{a,b{\}}^{*}\}$ is not context-free, by using Ogden's lemma on $a^{2p}\underset{\_}{b^{2p}}{a}^{2p}{b}^{2p}$.

And the given example last section $\{a^i{b}^j{c}^k{d}^l:i=0\text{ or }j=k=l\}$ is not context-free by using Ogden's lemma on $a{b}^{2p}\underset{\_}{c^{2p}}{d}^{2p}$.

Inherent ambiguity

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

Example: Let $L_0=\{a^n{b}^m{c}^m|m,n\ge 1\},L_1=\{a^m{b}^m{c}^n|m,n\ge 1\}$. The language $L=L_0\cup L_1$ is inherently ambiguous. (Example from page 3 of Ogden's paper.)

Similarly, $L^{*}$ is inherently ambiguous, and for any CFG of the language, letting $p$ be the constant for Ogden's lemma, we find that $(a^{p!+p}{b}^{p!+p}{c}^{p!+p}{)}^n$ has at least $2^n$ different parses. Thus $L^{*}$ has an unbounded degree of inherent ambiguity.

Undecidability

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)

Generalized condition

Bader and Moura have generalized the lemma to allow marking some positions that are not to be included in Template:Mvar. Their dependence of the parameters was later improved by Dömösi and Kudlek. If we denote the number of such excluded positions by Template:Mvar, then the number Template:Mvar of marked positions of which we want to include some in Template:Mvar must satisfy $d\ge p(e+1)$, where Template:Mvar is some constant that depends only on the language. The statement becomes that every Template:Mvar can be written as

$s=uvwxy$

with strings Template:Mvar and Template:Mvar, such that

1. Template:Mvar has at least one marked position and no excluded position,
2. Template:Mvar has at most $p^{(e+1)}$ marked positions, and
3. $u{v}^{n}w{x}^{n}y\in L$ for all $n\ge 0$.

Moreover, either each of Template:Mvar has a marked position, or each of $w,x,y$ has a marked position.