Next: Äquivalenzrelation und Minimalautomat 42
Up: Reguläre Sprachen (Typ 3)
Previous: Reguläre Ausdrücke 36
Contents
Index
Das Pumping Lemma
39
Das Pumping Lemma (Schleifenlemma, Lemma von
Bar-Hillel, -Theorem) ist
ein wichtiges Hilfsmittel, um zu Zeigen, das eine Sprache nicht regulär
ist.
Sei eine reguläre Sprache. Dann gibt es eine Zahl , so dass
sich alle Wörter mit
zerlegen lassen
in , so dass folgende Eigenschaften erfüllt sind:
Es gibt auch Sprachen die das Pumping Lemma erfüllen, und nicht regulär
sind. Das bedeutet, das mit dem Pumping Lemma nur das nicht regulärsein
von Sprachen gezeigt werden kann.
Umgekehrt gilt:
- Eine Sprache, bei der mehrere Exponenten in irgendwelchen Beziehungen
zueinander stehen, sind (laut Pumping Lemma) nicht regulär.
Marco Möller 18:11:27 24.10.2005