Wie funktioniert das Pumping-Lemma für reguläre Sprachen?
Also was genau kann ich daraus ableiten / prüfen?
2 Antworten
Mit dem Pumping-Lemma kann man nur zeigen, dass eine Sprache nicht regulär ist.
Das heißt man spielt in gewisser Weise ein Spiel nach den Regeln des Pumping Lemmas mit einem imaginären Gegner:
Du suchst dir ein Wort länger als n_0 aus der Sprache aus und musst ihm zeigen, dass er, selbst wenn er sich alle Mühe gibt, keine Zerlegung, die den Regeln entspricht, finden kann, sodass du dann nicht eine Zahl i sagen kannst, für die seine Zerlegung in Kombination mit deinem i ein Wort liefert, das nicht in der Sprache ist.
Dein Wort ist dabei leider immer sowas wie a^n b^n, und nicht etwa simpel wie aabb, da das dem |x| > n_0 nicht genügt, und der Gegner darf n_0 beliebig böse wählen.
Da es den Gegner nicht gibt, musst du nun auch noch selbst schlau sein und sagen, dass sämtliche, mögliche Zerlegungen nicht gehen. Der Trick ist, obwohl es beliebig viele Wörter der Form a^n b^n gibt, alle Zerlegungen mit Fallunterscheidungen abzudecken.
Zu jedem Fall kannst du eigentlich relativ schnell ein i finden, sodass es falsch ist (zumindest, wenn die Sprache wirklich nicht-regulär war).
Zu jeder regulären Sprache gibt es einen DFA und umgekehrt. Gibt es im Automaten einen Zyklus, so kann ich in diesem beliebig im Kreis laufen. Ich kann also den Wortteil, der diesem Zyklus entspricht beliebig aufpumpen.
Wenn wir uvw betrachten, und v genau einer Umrundung des Zyklus entspricht, dann kann ich eben uv+w ebenso erzeugen.