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.

Statement

Ogden's lemma states that if a language $L$ is context-free, then there exists some number $p\geq 1$ (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

s=uvwxy

with strings $u, v, w, x,$ and $y$ , such that

$vx$ has at least one marked position,
$vwx$ has at most $p$ marked positions, and
$uv^{n}wx^{n}y\in L$ for all $n\geq 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\}$ . Ogden's lemma can also be used to prove the inherent ambiguity of some languages.^{[citation needed]}

Generalized condition

Bader and Moura have generalized the lemma^[1] 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. If we denote the number of such excluded positions by $e$ , then the number $d$ of distinguished positions of which we want to include some in $vx$ must satisfy $d\geq p(e+1)$ , where $p$ is some constant that depends only on the language. The statement becomes that every $s$ can be written as

s=uvwxy

with strings $u, v, w, x,$ and $y$ , such that

$vx$ has at least one distinguished position and no excluded position,
$vwx$ has at most $p^{(e+1)}$ distinguished positions, and
$uv^{n}wx^{n}y\in L$ for all $n\geq 0$ .

Moreover, either each of $u,v,w$ has a distinguished position, or each of $w,x,y$ has a distinguished position.

References

^ Bader, Christopher; Moura, Arnaldo (April 1982). "A Generalization of Ogden's Lemma". Applied Mathematics and Computation. 29 (2): 404–407. doi:10.1145/322307.322315. Retrieved 7 July 2020.

Statement

Generalized condition

References

Further reading