Eine Technik der formalen Sprachen, die notwendige Bedingungen für die Regularität einer Sprache angibt, indem gezeigt wird, dass hinreichend lange Wörter so zerlegt werden können, dass ein mittlerer Teilblock mehrfach wiederholt (gepumpt) werden kann und die resultierenden Wörter weiterhin zur Sprache gehören.

Prinzip

Eine reguläre Sprache wird von einem endlichen Automaten erkannt; jede akzeptierende Berechnung auf einer genügend langen Eingabe muss einen Zustand zweimal besuchen, wodurch eine Schleife entsteht, deren wiederholtes Durchlaufen unendlich viele verwandte Wörter erzeugt. Diese Schleife liefert eine Zerlegung, die Pumpen eines Mittelblocks erlaubt.

Demonstration

Um die Sprache {a^n b^n : n ≥ 0} als nicht regulär zu zeigen, nimmt man das Gegenteil an und wendet das Pumpinglemma mit seiner Pumpenlänge an; jede vom Lemma geforderte Zerlegung führt zu gepumpten Wörtern mit ungleichen Zahlen von a's und b's, was der Zugehörigkeit widerspricht und die Nichtregularität beweist.

Fehlanwendung

Das Pumpinglemma als hinreichende Bedingung für Regularität zu verwenden (es ist nur notwendig) oder eine Zerlegung falsch zu wählen, ohne über alle vom Lemma geforderten Zerlegungen zu quantifizieren, sind häufige Fehler, die Beweise ungültig machen.

Konsequenz

Bietet eine praktische Methode, Nichtregularität von Sprachen zu beweisen und über die Grenzen endlicher Automaten zu argumentieren; es verdeutlicht, warum endlicher Speicher unbeschränkte Abhängigkeiten nicht erfassen kann.

Umkehrung

Die Umkehrung ist falsch: Eine Sprache, die die Pumpbedingung für eine bestimmte Pumpenlänge oder Zerlegung erfüllt, kann dennoch nicht regulär sein; feinere Werkzeuge (z. B. der Myhill–Nerode-Satz oder Ogdens Lemma) sind für genauere Unterscheidungen nötig.

Abgrenzung

Gilt nur für reguläre Sprachen (und über Abschlusseigenschaften für bestimmte Komplemente); kontextfreie Sprachen benötigen ein anderes Pumpinglemma, und das Lemma liefert keinen konstruktiven Automaten, wenn die Bedingungen fehlschlagen.

Semantische Spannung

Es besteht Spannung zwischen dem Pumpinglemma und anderen Charakterisierungen der Regularität: Myhill–Nerode liefert ein notwendiges‑und‑hinreichendes Kriterium via Äquivalenzrelation, während Pumpen nur eine notwendige strukturelle Eigenschaft ist und in Grenzfällen nicht schlüssig sein kann.

Synthese

Das Pumpinglemma formalisert die Begrenzung endlichen Speichers in endlichen Automaten: Jedes hinreichend lange akzeptierte Wort enthält ein wiederholbares Schleifensegment, das gepumpt werden kann, und die Verletzung dieser Eigenschaft beweist die Nichtregularität.