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 nicht regulär bzw. nicht kontextfrei ist.

Seinen Namen hat das Lemma vom englischen Begriff to pump, zu deutsch aufpumpen. Es leitet sich davon ab, dass Teile von Wörtern aus Sprachen bestimmter Klassen vervielfacht (aufgepumpt) werden können, so dass die dabei entstehenden Wörter ebenfalls in der Sprache sind.

Man unterscheidet zunächst zwischen dem Pumping-Lemma für reguläre Sprachen und jenem für kontextfreie Sprachen. In der Literatur sind weiterhin Pumping-Lemmata für Erweiterungen der kontextfreien Sprachen anzutreffen. Mächtigere Sprachklassen in der Chomsky-Hierarchie wie die kontextsensitiven Sprachen und auch die wachsend kontextsensitiven Sprachen ermöglichen jedoch kein Pumping-Lemma.

Alternativ wird das Lemma bzw. seine Ausprägungen auch als uvw-Theorem, uvwxy-Theorem, Schleifenlemma, Iterationslemma oder Lemma von Bar-Hillel bezeichnet.