Grenzen endlicher Automaten: das Pumping-Lemma
Lesen anpassen
Nach dieser Lektion kannst du
mit dem Schubfachprinzip begründen, warum ein langer Lauf eines DEA einen Zustand wiederholt,
das Pumping-Lemma für reguläre Sprachen mit seiner Quantorenstruktur genau aufschreiben und beweisen,
Nicht-Regularitätsbeweise als Spiel gegen einen Gegner führen, etwa für , Palindrome und ,
typische Fehler in solchen Beweisen erkennen und Abschlusseigenschaften als zweiten Weg nutzen.
Vorausgesetzt: Deterministische endliche Automaten (DEA), Nichtdeterministische Automaten und die Potenzmengenkonstruktion, Reguläre Ausdrücke und der Satz von Kleene
Kann ein endlicher Automat prüfen, ob in einem Wort gleich viele Zeichen a wie b stehen, die a alle vorn? Probierst du es aus, merkst du schnell das Problem: Nach dem Lesen der a muss der Automat wissen, wie viele es waren, und mit endlich vielen Zuständen kann er nur endlich viele Anzahlen auseinanderhalten.
Das ist eine gute Ahnung, aber noch kein Beweis. Dass dir kein Automat einfällt, heißt nicht, dass es keinen gibt. In dieser Lektion machst du aus der Ahnung ein Werkzeug: Du zeigst, dass jede reguläre Sprache eine bestimmte Wiederholungseigenschaft hat, das Pumping-Lemma. Fehlt einer Sprache diese Eigenschaft, kann sie nicht regulär sein. Gemeint ist die Sprache ; dabei steht für aufeinanderfolgende a, und ist das leere Wort .
Ein DEA hat Zustände und liest ein Wort der Länge . Der Lauf ist die Folge der Zustände, die er dabei durchläuft, den Startzustand mitgezählt. Was kannst du sicher sagen, ohne den Automaten zu kennen?
Eine Schleife im Lauf
Eine Schleife im Lauf
Der Automat „Binärzahl modulo 3“ hat die Zustände ; der Zustand bedeutet „die bisher gelesene Binärzahl hat beim Teilen durch den Rest “. Endzustand ist . Für das Wort (dezimal ) ist der Lauf
.
Der Zustand kommt nach dem ersten und nach dem dritten Zeichen vor. Das Stück dazwischen führt also von zurück nach , es ist eine Schleife. Wir zerlegen das Wort in (bis zur Schleife), (die Schleife) und (der Rest).
Dabei ist das Wort , -mal hintereinander geschrieben, und . Weil von nach führt, ist es dem Automaten gleich, wie oft er die Schleife durchläuft: Nach steht er immer in , und bringt ihn dann nach . Alle Wörter werden angenommen, und tatsächlich sind , und durch teilbar.
Der Pfeil von links zeigt den Start. Ein Doppelkreis ist ein Zustand, in dem ein Wort angenommen wird. Der hervorgehobene Zustand ist gerade aktiv.
- 1
- 0
- 0
- 1
Start. Der Automat steht in q0. Drücke „Schritt“, um das erste Zeichen zu lesen.
Probier es aus
Pumping-Lemma für reguläre Sprachen
Sei eine reguläre Sprache. Dann gibt es eine Zahl , sodass sich jedes Wort mit Länge so in drei Teile zerlegen lässt, dass gilt:
- (die Schleife beginnt und endet in den ersten Zeichen),
- (die Schleife ist nicht leer),
- für alle (man darf die Schleife beliebig oft durchlaufen oder weglassen).
Die Zahl heißt Pumping-Konstante. Als Formel, mit für „es gibt“ und für „für alle“:
Beweisidee: Das Beispiel oben, allgemein aufgeschrieben.
Weil regulär ist, gibt es einen DEA mit . Wir schreiben für den Zustand, in dem steht, wenn er in beginnt und das Wort liest; insbesondere ist . Setze , die Zahl der Zustände.
Sei mit . Betrachte die Zustände und für . Das sind Einträge, aber es gibt nur Zustände. Nach dem Schubfachprinzip gibt es Indizes mit .
Setze , und . Dann ist , und .
Nach Konstruktion gilt und . Mit Induktion über folgt für alle : Für ist das die erste Gleichung, und aus folgt .
Also ist , denn . Damit ist für alle .
Das Pumping-Spiel
Um zu zeigen, dass nicht regulär ist, verneinst du die Aussage des Lemmas. Beim Verneinen wird jedes zu und umgekehrt, die Reihenfolge bleibt:
Für jedes gibt es ein mit , sodass für jede Zerlegung mit und ein existiert mit .
Das liest man am besten als Spiel. Die „für alle“-Stellen wählt ein Gegner, der dir schaden will; die „es gibt“-Stellen wählst du. Du gewinnst, wenn du jede mögliche Wahl des Gegners beantworten kannst.
| Zug | Wer | Was wird gewählt |
|---|---|---|
| 1 | Gegner | eine Zahl |
| 2 | du | ein Wort mit , abhängig von |
| 3 | Gegner | eine Zerlegung mit , |
| 4 | du | ein mit |
Hast du eine Gewinnstrategie, erfüllt das Pumping-Lemma nicht und ist daher nicht regulär.
Im Pumping-Spiel für eine Sprache : Welche Wahl triffst du?
ist nicht regulär
ist nicht regulär
Wir spielen das Spiel und zeigen, dass du jede Wahl des Gegners beantworten kannst.
Der Gegner wählt ein beliebiges .
Palindrome sind nicht regulär
Palindrome sind nicht regulär
Ein Palindrom ist ein Wort, das rückwärts gelesen gleich bleibt; mit für das umgedrehte Wort ist das . Sei .
Zum gegebenen wählst du . Es ist ein Palindrom mit . Für jede Zerlegung mit liegen und im vorderen a-Block, also mit . Mit entsteht
Die beiden Wörter sind verschieden, weil das b an verschiedenen Stellen steht (). Also ist , und ist nicht regulär. Beachte die Wahl von : Das einzelne b in der Mitte sorgt dafür, dass der Gegner nur im vorderen Block zerlegen kann. Mit , ebenfalls ein Palindrom, verlierst du dagegen: Jedes ist ein Palindrom, egal wie gepumpt wird.
Quadratzahlen:
Quadratzahlen:
Hier hilft keine Reihenfolge der Zeichen, denn es gibt nur eines. Das Argument läuft über die Länge.
Zum gegebenen wählst du ; es ist .
Selbst ein wählen oder nur eine Zerlegung prüfen
Selbst ein wählen oder nur eine Zerlegung prüfen
Zwei Fehlschlüsse kommen in Klausuren immer wieder vor:
- „Sei . Dann ist …“ Das zeigt nur, dass die Konstante nicht passt. Der Automat könnte Zustände haben.
- „Zerlege als , , ; dann ist .“ Erstens verletzt diese Zerlegung , zweitens ist das nur eine von vielen. Das Lemma behauptet die Existenz einer guten Zerlegung, also musst du alle zulässigen widerlegen.
Das bleibt eine Variable, über die du nichts weißt außer . Das Wort hängt von ab. Die Zerlegung beschreibst du allgemein ( mit ), sodass dein Argument jede Wahl des Gegners abdeckt.
Das Pumping-Lemma ist nur notwendig
Es gibt Sprachen, die das Pumping-Lemma erfüllen und trotzdem nicht regulär sind. Ein Beispiel über :
.
Das Pumping-Lemma kann also nur Nicht-Regularität zeigen, nie Regularität.
erfüllt das Lemma mit . Sei mit . Wähle , = das erste Zeichen von und = den Rest; dann ist und .
Beginnt mit a, ist mit , und . Für liegt das im ersten Teil von , für ist es und liegt im zweiten Teil.
Beginnt mit b oder c, ist , und Pumpen des ersten Zeichens ergibt wieder ein Wort aus , also aus dem zweiten Teil.
ist nicht regulär. Wäre regulär, dann auch , denn reguläre Sprachen sind unter Schnitt abgeschlossen. Aus einem DEA dafür erhält man einen DEA für , indem man den Startzustand durch ersetzt. Diese Sprache ist aber nicht regulär; der Beweis ist derselbe wie für .
Abschlusseigenschaften als zweiter Weg
Abschlusseigenschaften als zweiter Weg
Oft ist es kürzer, eine Sprache auf eine schon bekannte nicht reguläre Sprache zurückzuführen. Sei .
Angenommen, wäre regulär. Die Sprache ist regulär (sie hat einen regulären Ausdruck), und reguläre Sprachen sind unter Schnitt abgeschlossen. Dann wäre auch
regulär, im Widerspruch zum Beweis oben. Also ist nicht regulär. Genauso kannst du mit dem Komplement arbeiten: Ist regulär, so auch . Und auch die Sprache aus dem letzten Satz ließ sich nur so als nicht regulär entlarven, weil das Pumping-Lemma bei ihr versagt.
Die Sprache erfüllt das Pumping-Lemma mit der Konstante . Was folgt daraus?
Zusammenfassung
Schubfachprinzip: Ein Lauf eines DEA mit Zuständen auf mindestens Zeichen wiederholt einen Zustand; das Stück dazwischen ist eine Schleife.
Pumping-Lemma: Ist regulär, gibt es , sodass jedes mit eine Zerlegung mit , und für alle hat.
Nicht-Regularität als Spiel: Der Gegner wählt und die Zerlegung, du wählst (abhängig von ) und .
Mit diesem Spiel sind , die Palindrome und nicht regulär.
Typische Fehler: ein festes einsetzen, nur eine Zerlegung prüfen, ungeschickt wählen.
Das Lemma ist nur notwendig: Es gibt nicht reguläre Sprachen, die es erfüllen.
Abschlusseigenschaften (Schnitt mit einer regulären Sprache, Komplement) führen oft schneller zum Ziel.
Übungen
Welche Formel ist die Verneinung der Pumping-Eigenschaft, also das, was du für eine nicht reguläre Sprache zeigst? (Die Bedingungen an und die Zerlegung sind jeweils mitgemeint.)
Der Automat „Binärzahl modulo 3“ aus der Lektion liest . Nimm wie im Beweis die erste Stelle, an der sich ein Zustand im Lauf wiederholt, und zerlege . Welchen Dezimalwert hat die Binärzahl ?
Im Spiel für hat der Gegner gewählt, und du hast gewählt. Welche Zerlegung darf der Gegner nicht wählen?
Zeige mit dem Pumping-Lemma, dass nicht regulär ist.
Zeige ohne Pumping-Lemma, nur mit Abschlusseigenschaften und dem Ergebnis für , dass nicht regulär ist.
Zeige, dass nicht regulär ist.