# 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.

Ogden's lemma states that if a language ${\displaystyle L}$ is context-free, then there exists some number ${\displaystyle p\geq 1}$ (where ${\displaystyle p}$ may or may not be a pumping length) such that for any string ${\displaystyle s}$ of length at least ${\displaystyle p}$ in ${\displaystyle L}$ and every way of "marking" ${\displaystyle p}$ or more of the positions in ${\displaystyle s}$, ${\displaystyle s}$ can be written as

${\displaystyle s=uvwxy}$

with strings ${\displaystyle u,v,w,x,}$ and ${\displaystyle y}$, such that

1. ${\displaystyle vx}$ has at least one marked position,
2. ${\displaystyle vwx}$ has at most ${\displaystyle p}$ marked positions, and
3. ${\displaystyle uv^{n}wx^{n}y\in L}$ for all ${\displaystyle 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 ${\displaystyle \{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 Ogden's Condition

Bader and Moura have generalized the lemma to allow marking some positions that are not to be included in ${\displaystyle 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 ${\displaystyle e}$, then the number ${\displaystyle d}$ of distinguished positions of which we want to include some in ${\displaystyle vx}$ must satisfy ${\displaystyle d\geq p(e+1)}$, where ${\displaystyle p}$ is some constant that depends only on the language. The statement becomes that every ${\displaystyle s}$ can be written as

${\displaystyle s=uvwxy}$

with strings ${\displaystyle u,v,w,x,}$ and ${\displaystyle y}$, such that

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

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