Ogden's lemma

From Wikipedia, the free encyclopedia
Jump to navigation Jump to 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 is context-free, then there exists some number (where may or may not be a pumping length) such that for any string of length at least in and every way of "marking" or more of the positions in , can be written as

with strings and , such that

  1. has at least one marked position,
  2. has at most marked positions, and
  3. for all .

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 . Ogden's lemma can also be used to prove the inherent ambiguity of some languages[citation needed].

Generalized Ogden's Condition[edit]

Bader and Moura have generalized the lemma to allow marking some positions that are not to be included in . Their dependence of the parameters was later improved by Dömösi and Kudlek. If we denote the number of such excluded positions by , then the number of distinguished positions of which we want to include some in must satisfy , where is some constant that depends only on the language. The statement becomes that every can be written as

with strings and , such that

  1. has at least one distinguished position and no excluded position,
  2. has at most distinguished positions, and
  3. for all .

Moreover, either each of has a distinguished position, or each of has a distinguished position.

See also[edit]

References[edit]

  • Bader, C., and Moura, A. (1982). "A generalization of Ogden's lemma". J. Assoc. Comput. Mach. 29 (2): 404–407. doi:10.1145/322307.322315.CS1 maint: Multiple names: authors list (link)
  • Dömösi, P., and Kudlek, M. (1999). "Strong Iteration Lemmata for Regular, Linear, Context-Free, and Linear Indexed Languages". FCT'99, LNCS. 1684: 226–233. doi:10.1007/3-540-48321-7_18.CS1 maint: Multiple names: authors list (link)
  • 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.