Ogden's lemma

From Wikipedia, the free encyclopedia

In the theory of formal languages, Ogden's lemma provides an extension of flexibility over the pumping lemma for context-free languages.

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

w = uvxyz

with strings u, v, x, y, and z, such that vy has at least one marked position (ie |vy| > 0), vxy has at most p marked positions, and

uvⁱxyⁱz is in L for every i ≥ 0.

Ogden's lemma can be used to show that certain languages are not context-free, in cases where the pumping lemma for context-free languages is not sufficient. An example is the language {aⁱb^jc^kd^l : i = 0 or j = k = l}.

Observe that when every position is marked, this lemma is equivalent to the pumping lemma for context-free languages.

[edit] See also

• Pumping lemma
• Pumping lemma for context-free languages
• Pumping lemma for regular languages

[edit] References

• Ogden, W. (1968). "A helpful result for proving inherent ambiguity". Mathematical Systems Theory 2: 191–194. doi:10.1007/BF01694004. 

• Hopcroft, Motwani and Ullman (1979). Automata Theory, Languages, and Computation. Adison Wesley.