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

We 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 L is context-free, then there exists some number

p

≥

1

{\displaystyle 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

=

u

v

w

x

y

{\displaystyle 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

u

v

n

w

x

n

y

∈

L

{\displaystyle uv^{n}wx^{n}y\in L}

for all

n

≥

0

{\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

{

a

i

b

j

c

k

d

l

:

i

=

0

or

j

=

k

=

l

}

{\displaystyle \{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

≥

1

}

{\displaystyle \{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}}

is a standard example of non-context-free language,

Similarly, one can prove the "copy twice" language

L

=

{

w

2

|

w

∈

{

a

,

b

}

∗

}

{\displaystyle L=\{w^{2}|w\in \{a,b\}^{*}\}}

is not context-free, by using Ogden's lemma on

a

2

p

b

2

p

_

a

2

p

b

2

p

{\displaystyle a^{2p}{\underline {b^{2p}}}a^{2p}b^{2p}}

.