Pumping lemma

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 can be broken into pieces, some of which can be repeated arbitrarily to produce a longer string in the language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.

The two most important examples are the pumping lemma for regular languages and the pumping lemma for context-free languages. Ogden's lemma is a second, stronger pumping lemma for context-free languages.

These lemmas can be used to determine if a particular language is "not" in a given language class. However, they cannot be used to determine if a language is in a given class, since satisfying the pumping lemma is a necessary, but not sufficient, condition for class membership.

References

* Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Pumping-Lemma — Das Pumping Lemma bzw. Pumplemma (auch Schleifensatz genannt) beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache… …   Deutsch Wikipedia

  • Pumping Lemma — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch 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 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 — can refer to: *The operation of a pump, for moving a liquid from one location to another **The use of a breast pump or milking machine for extraction of milk *Pumping (oil well), injecting chemicals into a wellbore *Pumping (computer systems),… …   Wikipedia

  • 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… …   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

  • PumpingLemma — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

  • Pumpinglemma — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

  • Pumplemma — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

Share the article and excerpts

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