Ogden's lemma

In the theory of formal languages, Ogden's lemma (named after William F. Ogden) 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 = uxyzv

with strings u, x, y, z, and v, such that

  1. xz has at least one marked position,
  2. xyz has at most p marked positions, and
  3. uxiyziv 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 {aibjckdl : i = 0 or j = k = l}. It is also useful to prove the inherent ambiguity of some languages.

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

See also

References

This article is issued from Wikipedia - version of the Saturday, March 19, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.