Ogden's lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 L is context-free, then there exists some number p ≥ 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 = uvwxy

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

  1. vwx has at most p marked positions,
  2. vx has at least one marked position, and
  3. uvnwxnyL for all n ≥ 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 {aibjckdl : i = 0 or j = k = l}. Ogden's lemma can also be used to prove the inherent ambiguity of some languages.

See also[edit]

References[edit]

  • Ogden, W. (1968). "A helpful result for proving inherent ambiguity". Mathematical Systems Theory. 2 (3): 191–194. doi:10.1007/BF01694004. 
  • Hopcroft, Motwani and Ullman (1979). Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 81-7808-347-7.