Ogden's lemma

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

  • 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 8178083477. 

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Pumping lemma for context-free languages — The pumping lemma for context free languages, also known as the Bar Hillel lemma, is a lemma that gives a property that all context free languages have. Its primary use is to prove a language is not context free.The pumping lemma for context free …   Wikipedia

  • Pumping lemma for regular languages — In the theory of formal languages, the pumping lemma for regular languages describes an essential property of all regular languages. Informally, it says that all sufficiently long words in a regular language may be pumped that is, have a middle… …   Wikipedia

  • Pumping lemma — In the theory of formal languages in computability theory, a pumping lemma states that any infinite language of a given class can be pumped and still belong to that class. A language can be pumped if any sufficiently long string in the language… …   Wikipedia

  • Ogdens Lemma — ist eine Methode der theoretischen Informatik, mit der gezeigt werden kann, dass eine formale Sprache keine kontextfreie Sprache ist, da sie Eigenschaften beschreibt, die für alle kontextfreien Sprachen gelten müssen. Es liefert somit nur eine… …   Deutsch Wikipedia

  • List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia

  • List of mathematics articles (O) — NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… …   Wikipedia

  • Lemme de l'étoile — En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, lemme de la pompe, pumping lemma en anglais) énonce une propriété typique de tout langage rationnel. Informellement, il stipule que tout mot… …   Wikipédia en Français

  • List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia

  • Frank P. Ramsey — Infobox Philosopher region = United Kingdom era = 20th century color = #B0C4DE image size = 200px image caption = name = Frank P. Ramsey birth = 22 February 1903 death = 19 January 1930 school tradition = Analytic philosophy main interests =… …   Wikipedia

  • Autosegmental phonology — is the name of a framework of phonological analysis proposed by John Goldsmith in his PhD thesis in 1976 at the Massachusetts Institute of Technology (MIT).As a theory of phonological representation, autosegmental phonology developed a formal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”