Ogden's Lemma

In formal language theory, the Ogden lemma provides an extension of the flexibility of the sprawl lemma for context-free languages .

Ogden's lemma states that if the language L is context-free, then there exists a number p > 0 (where p may or may not be the pump length), such that for any string w of length at least p from L and for any markups » p or more positions in w , w can be represented as

w = uvxyz

where u , v , x , y , and z are strings such that

1. x contains at least one marked position,
2. either u and v contain the marked position, or both y and z contain it,
3. vxy contains at most p marked positions, and
4. uv ⁱ xy ⁱ z belongs to L for any i ≥ 0.

The Ogden lemma can be used to prove that a given language is not context-free, in cases where the expansion lemma is not enough for context-free languages . An example would be the language { a ⁱ b ^j c ^k d ^l : i = 0 or j = k = l }. It is also useful for proving the substantial ambiguity of some languages.

Note that if all positions are marked, this lemma is equivalent to the pumping lemma for context-free languages.