Mittlerweile haben wir mit DFAs, NFAs, \(\lambda\)-NFAs und regulären Ausdrücken vier verschiedene Formalismen kennen gelernt, die die Familie der regulären Sprachen erfassen, d.h. jede von einem dieser drei Automatenmodelle akzeptierte und jede von einem regulären Ausdruck beschriebene Sprache, ist eine reguläre Sprache. Wir haben dann noch die Abschlusseigenschaften kennengelernt und gesehen, dass es auch gar nicht so leicht ist, keine reguläre Sprache mehr zu haben. Vereinigt man z.B. zwei reguläre Sprachen, so hat man wieder eine, ebenso beim Durchschnitt und auch das Komplement einer regulären Sprache ist stets regulär.
Es erscheint aber unwahrscheinlich, dass alle Sprachen regulär sind. Der DFA kann ja nur endlich viele Informationen speichern und sich auch keine Informationen mehrmals ansehen. Intuitiv kann man also gut vermuten, dass es doch Sprachen geben sollte, die nicht regulär sind. Aber wie könnte eine solche Sprache aussehen? Und wie beweist man, dass eine Sprache tatsächlich nicht regulär ist?
Da ein endlicher Automat nur endlich viele Informationen speichern kann, sollten wir dann an die Grenzen endlicher Automaten stossen, wenn wir uns unendlich viele Informationen merken müssen bzw. zwar endlich viele, aber von der Länge des Eingabewortes abhängig viele Informationen. Müssten wir uns z.B. bei einem Eingabewort der Länge \(10\) gerade \(10\) Informationen merken, bräuchten wir \(10\) Zustände. Ist das dann aber auch für ein Eingabewort der Länge \(100\) und \(1000\) nötig, dann gibt es keine obere Grenze für die Zustände und es kann keinen endlichen Automaten für die Sprache geben.
Ein guter Kandidat ist daher vielleicht die Sprache \(L = \{a^n b^n \mid n \in \mathbb{N}\}\). Diese Sprache ist nicht zu kompliziert zu beschreiben und dennoch erfüllt sie intuitiv obiges. Wenn wir nämlich die \(n\) \(b\)s lesen wollen, so müssen wir uns vorher die Zahl \(n\) merken, also die Anzahl der gelesenen \(a\)s und diese Zahl ist wie oben gewünscht abhängig von der Wortlänge. Wir müssten einen Zustande haben, in dem wir uns merken, dass wir ein \(a\) gelesen haben, einen, in dem wir uns merken, dass es zwei waren usw. Da die Zahl beliebig groß werden kann, kann es intuitiv keinen DFA geben, der sich alle diese Zahlen in seinen nur endlich vielen Zuständen merkt.
Dies ist aber zunächst nur eine Intuition. Wie beweisen wir nun, dass obiges \(L\) tatsächlich nicht regulär ist? Hier hilft uns das sogenannte Pumping Lemma.
Das Pumping Lemma
Das Pumping Lemma macht eine Aussage über alle regulären Sprachen, d.h. es beschreibt eine Eigenschaft, die alle regulären Sprachen haben. Hat eine Sprache diese Eigenschaft also nicht, so kann sie nicht regulär sein. Um uns dem Pumping Lemma zu nähern, machen wir uns einmal selbst auf die Suche nach einer Eigenschaft \(X\), die jede reguläre Sprache haben muss. Wir wissen bisher von regulären Sprachen, das es zu jeder reglären Sprache einen DFA gibt, der sie akzeptiert. Von DFAs wiederum wissen wir, dass sie nur endlich viele Zustände haben. Dies können wir versuchen auszunutzen.
Legt man einem Automaten mit \(n\) Zuständen ein Wort vor, dass z.B. die Länge \(4 \cdot n\) hat, dann muss der Automat, wenn er das Wort akzeptiert, mindestens einen Zustand mehrfach besuchen. Bei jedem gelesene Symbol findet ja ein Zustandswechsel statt und wenn man \(4 \cdot n\) Symbole liest, finden also \(4 \cdot n\) Zustandswechsel statt. Hat man nur \(n\) Zustände zur Auswahl muss zwangsläufig mindestens einer mehrfach auftreten. Das heißt auch, dass beim Lesen des Wortes der Automat Schleifen durchwandert. Diese Schleifen könnte man mehrfach entlang gehen und so neue Worte erzeugen, die alle auch in der Sprache sein müssten. Damit haben wir eine schöne Eigenschaft regulärer Sprachen gefunden. Für alle Worte der Sprache ab einer bestimmten Länge muss gelten, dass man sie so zerlegen kann, dass ein Teilstück des Wortes beliebig oft wiederholt werden kann und das Wort dennoch weiterhin in der Sprache ist.
Hätte man für \(L\) einen Automaten mit \(k\) Zuständen, dann betrachtet man \(a^k b^k\). Nach obigem müsste schon beim Lesen der ersten \(k\) Symbole (also der \(a\)s) ein Zustand mehrfach auftreten, d.h. wir haben dann bereits beim Lesen der \(a\)s eine Schleife und könnten diese Schleife auch mehrfach entlang gehen. Nach obigem Überlegungen müssten die dabei entstehenden Wort ja alle in der Sprache \(L\) sein (da sie ja weiterhin von unserem angenommenen Automaten akzeptiert werden müssten). Dies klappt aber nicht, da wir ja Worte der Art \(a^{k+j} b^k\) erzeugen würden, die gerade nicht in \(L\) sind.
Die oben erarbeitete Vorstellung der speziellen Eigenschaft aller regulären Sprachen wird nachfolgend im Pumping Lemma formalisiert und bewiesen. Im Beweis finden sich etliche der oben schon angedeuteten Argumente wieder. Im Anschluss an den Beweis nutzen wir das Pumping Lemma dann, um für \(L = \{a^n b^n \mid n \in \mathbb{N}\}\) eindeutig nachzuweisen, dass diese Sprache nicht regulär ist. Auch in dem Beweis finden sich dann die Überlegungen von eben als überzeugende Argumente wieder.
Lemma 2.4.1 (Pumping Lemma)
Sei \(L \in \text{REG}\) eine reguläre Sprache. Dann gibt es ein \(n \geq 1\), so dass jedes Wort \(z \in L\) mit \(|z| \geq n\) in die Form \(z = uvw\) zerlegt werden kann, wobei- \(|uv| \leq n\)
- \(|v| \geq 1\)
- \(uv^iw \in L\) für jedes \(i \in \mathbb{N}\) (inkl. der \(0\))
(Äquivalent zur letzten Aussage ist die Aussage \(\{u\}\{v\}^*\{w\} \subseteq L\).)
Bevor wir zum Beweis kommen, betrachten wir das Lemma noch einmal genauer. Wie oben in den Überlegungen schon beschrieben, macht es eine Aussage über reguläre Sprachen. Wenn eine Sprache also regulär ist, dann gilt das Pumping Lemma. Es sagt dann, dass es eine natürliche Zahl \(n \geq 1\) gibt derart, dass jedes Wort \(z\) aus \(L\), das mindestens die Länge \(n\) hat, zerlegt werden kann in \(z = uvw\).
Die Zerlegung \(z = uvw\) aus dem Pumping Lemma erfüllt dann drei Eigenschaften, von denen wir die dritte oben bereits skizziert haben: Man kann einen Teil des Wortes (hier das \(v\)) beliebig oft schreiben und erhält stets ein Wort aus \(L\). Das Wort \(v\) entspricht im Automaten aus den vorherigen Überlegungen der Schleife. Dies wird auch gleich im Beweis deutlich werden. Die erste und zweite Eigenschaft besagen, dass die Schleife existieren muss, also mindestens die Länge \(1\) haben muss (zweite Eigenschaft) und dass diese bis zu einem bestimmten Zeitpunkt das erste Mal entlang gegangen sein muss (erste Eigenschaft). Die erste Eigenschaft rührt daher, dass bei einem Automaten mit \(n\) Zuständen nach \(n\) gelesenen Symbolen bereits \(n+1\) Zustände besucht wurden (der Startzustand und nach jedem gelesenen Symbol ein weiterer). Hat man nur \(n\) Zustände ist spätestens der \(n+1\)-te Zustand also ein Zustand, den man schon einmal besucht hatte.
Man beachte noch, dass die dritte Eigenschaft besagt, dass mit \(z = uvw \in L\) für jedes \(i \geq 0\) auch \(uv^iw \in L\) gilt. Insbesondere kann \(i\) auch \(0\) sein und in diesem Fall haben wir \(uv^0w = uw\). Es müssen also \(uw\) ebenso wie \(uvvw\), \(uvvvw\) usw. alle in \(L\) sein.
Wir beweisen nun das Pumping Lemma. Man achte beim Durcharbeiten darauf, wo sich die obigen Ideen überall wiederfinden.
Beweis
Sei \(L\) regulär. Dann gibt es einen DFA, der \(L\) akzeptiert und sogar einen vollständigen DFA, der \(L\) akzeptiert. Sei dieser vollständige DFA mit \(A\) benannt. Es gilt also \(L(A) = L\) und \(A\) ist zudem vollständig. \(A\) hat eine Menge von Zuständen. Sei \(n\) die Anzahl dieser Zustände von \(A\). Wir müssen nun zeigen, dass jedes Wort \(z\) aus \(L\), dessen Länge mindestens \(n\) ist, in \(z = uvw\) zerlegt werden kann, wobei \(u\), \(v\) und \(w\) die drei Eigenschaften des Lemmas erfüllen.Sei also \(z \in L\) mit \(|z| \geq n\) (gibt es kein solches \(z\) ist nichts zu zeigen, da das Pumping Lemma ja nur für Worte mit dieser Eigenschaft etwas fordert; gibt es also keine solchen Worte, gilt das Pumping Lemma sofort). Wir legen nun \(A\) das Wort \(z\) vor. \(A\) beginnt dann eine Rechnung in seinem Startzustand \(z_s\). Da \(A\) vollständig ist kann \(z\) bis zum Ende gelesen werden. (Ferner endet \(A\) dann in einem Endzustand, da \(z \in L\) ist. Dies benötigen wir aber jetzt noch nicht.) Da \(z\) aus mindestens \(n\) Buchstaben besteht, finden mindestens \(n\) Zustandsübergänge statt, d.h. es werden inklusive des Startzustandes mindestens \(n+1\) Zustände besucht. Da es aber nur \(n\) Zustände gibt, muss mindestens ein Zustand doppelt auftreten.
Sei die Zustandsfolge, die in \(A\) vom Startzustand \(z_s\) zu einem Endzustand \(z_e\) beim Lesen von \(z\) besucht wird durch \(z_0, z_1, z_2, \ldots, z_n, \ldots, z_q\) gegeben. Hier ist also \(z_0 = z_s\) und \(z_q = z_e\) und die Indizes geben an, der wievielte Zustand gerade besucht wird. Man beachte, dass die Indizierung hier nichts mit den verschiedenen Zuständen aus \(Z\) zu tun hat. Es könnte also z.B. \(z_1 = z_2\) sein. Wir wissen nun nach obigem, dass ein Zustand mehrfach auftreten muss. Seien daher \(z_i\) und \(z_j\) mit \(i \not= j\) und \(i < j\) in dieser Folge gleich und außerdem \(z_j\) der erste Zustand, der ein zweites Mal auftritt. Da von \(z_0\) bis \(z_n\) bereits \(n+1\) Zustände in der Zustandsfolge auftreten, es aber nur \(n\) Zustände gibt, muss hier bereits ein Zustand doppelt auftreten, d.h. es muss \(j \leq n\) gelten. Ferner muss wegen \(i \not= j\) und \(i < j\) (\(z_i\) und \(z_j\) treten in der Folge nicht zum gleichen Zeitpunkt auf und \(z_j\) ist gerade die erste Wiederholung von \(z_i\)) \(j – i \geq 1\) gelten.
Wir können nun das Wort \(z\), das uns ja von \(z_0\) nach \(z_q\) in der obigen Zustandsfolge bringt, an \(i\) und \(j\) zerlegen. Sei dazu
- \(u\) das Wort, das von \(z_0\) bis \(z_i\) gelesen wird,
- \(v\) das Wort, das von \(z_i\) bis \(z_j\) gelesen wird und
- \(w\) das Wort, das von \(z_j\) bis \(z_q\) gelesen wird.
Damit ist \(uvw = z\). Nach obigen Ausführungen zur Wahl von \(i\) und \(j\) ist ferner \(|uv| \leq n\) (wegen \(j \leq n\) oben) und \(|v| \geq 1\) (wegen \(j-i \geq 1\) oben). Die gewählte Zerlegung von \(z\) in \(uvw\) erfüllt also schon die ersten beiden Bedingungen im Pumping Lemma.
Da \(z_i = z_j\) gilt, aber \(i \not= j\) ist, überführt das Wort \(v\) den Automaten also von \(z_i\) zurück nach \(z_i (= z_j)\). Diese Schleife (bzw. besser: dieser Kreis) im Automaten kann beliebig oft entlang gegangen werden und egal wie oft man diese Schleife entlang geht, also egal wie oft man das Teilwort \(v\) liest, man ist im Anschluss in \(v_j\) und kann von hieraus mit \(w\) in einen Endzustand gelangen (erst an dieser Stelle wird benötigt, dass \(v_q\) ein Endzustand ist, da ursprünglich ja auch \(v\) von \(A\) akzeptiert wurde). Daraus folgt aber nun, dass \(u v^i w\) für alle \(i \geq 0\) akzeptiert wird und also auch die dritte Bedingung im Pumping Lemma von unserer gewählten Zerlegung erfüllt wird. Damit haben wir das Pumping Lemma bewiesen.
Wir wollen nun das Pumping Lemma nutzen, um zu zeigen, dass die Sprache \(\{a^n b^n \mid n \in \mathbb{N}\}\) nicht regulär ist. Dazu nehmen wir an, die Sprache wäre regulär und zeigen einen Widerspruch. Wir führen den Beweis zunächst sehr ausführlich und bauen etliche Erklärungen in den Beweis ein. Wir betonen aber schon hier, dass wir bei einem Widerspruchsbeweis annehmen, dass das Pumping Lemma gilt und dann einen Widerspruch herstellen wollen. Da das Pumping Lemma sagt, dass alle Worte mit \(z \in L\) und \(|z| \geq n\) zerlegt werden können, genügt es für ein Wort mit \(z \in L\) und \(|z| \geq n\) zu zeigen, dass dem nicht so ist. Da das Pumping Lemma dann sagt, dass eine Zerlegung \(z = uvw\) existiert, die die drei Eigenschaften erfüllt (also erstens \emph{und} zweitens und drittens), muss man dann zeigen, dass jede Zerlegungen von \(z\) in \(uvw\) mindestens eine der drei Eigenschaften nicht erfüllt (also alle Zerlegungen im Widerspruch zu erstens, zweitens oder drittens stehen).
Satz 2.4.2
\(L := \{a^n b^n \mid n \in \mathbb{N}\}\) ist nicht regulär.Beweis
Angenommen \(L\) wäre regulär. Dann gilt das Pumping Lemma. Sei \(k\) die Zahl aus dem Pumping Lemma.
Wir betrachten nun das Wort \(z = a^k b^k\). Es gilt \(z \in L\) und \(|z| \geq k\).
Nun muss es nach dem Pumping Lemma eine Zerlegung \(z = uvw\) geben, die die drei Eigenschaften erfüllt. Wir wollen dies zum Widerspruch führen. Wir betrachten dazu nun nur jene Zerlegungen, die die erste und zweite Bedingung erfüllen und zeigen, dass diese im Widerspruch zur dritten stehen. Wir haben dann gezeigt, dass jede Zerlegung von \(z\) in \(uvw\) im Widerspruch zu einer der drei Bedingungen steht und sind dann fertig.
Warum müssen hier alle Zerlegungen betrachtet werden? Im Pumping Lemma ist ja nur von einer die Rede? Letzteres ist zwar richtig, wir wollen ja aber gerade einen Widerspruch erzeugen. Um also zu zeigen, dass es nicht stimmt, dass es eine Zerlegung von \(z\) in \(uvw\) gibt, die die drei Eigenschaften erfüllt, müssen wir zeigen, dass es keine solche Zerlegung gibt. Dazu müssen wir zeigen, dass alle Zerlegungen einen Widerspruch erzeugen, dass also jede Zerlegung von \(z\) in \(uvw\) mit mindestens einer der drei Eigenschaften im Widerspruch steht.
Und warum genügt es dann nur jene zu betrachten, die die ersten beiden Eigenschaften erfüllen? Das ist ganz einfach: Eine Zerlegung, die nicht die ersten beiden Eigenschaften erfüllt, erfüllt ja bereits mindestens eine der drei Eigenschaften nicht (nämlich eine der ersten beiden). Es genügt also sich die Zerlegungen anzugucken, die die beiden ersten Eigenschaften erfüllen und dann herzuleiten, dass diese Zerlegungen nun aber im Widerspruch zur dritten Eigenschaft stehen. Damit hat man dann gezeigt, dass alle Zerlegungen zu den drei Eigenschaften im Widerspruch stehen. Entweder widerspricht eine Zerlegung dann schon einer der ersten beiden Eigenschaften oder, wenn sie die ersten beiden Eigenschaften erfüllt, dann widerspricht sie der dritten.
Der Grund für dieses Vorgehen ist, dass man über Zerlegungen, die die ersten beiden Eigenschaften erfüllen schon etwas weiß (nämlich die Aussagen der ersten beiden Eigenschaften) und dass man dann damit arbeiten kann.
Sei also \(z = a^k b^k = uvw\) eine Zerlegung mit \(i) |uv| \leq k\) und \(ii) |v| \geq 1\). Da \(uv\) ja in den ersten Buchstaben von \(z\) liegt (wgen \(z = uvw\)) und da \(uv\) aber höchstens die Länge \(k\) hat, muss \(uv\) also in den ersten \(k\) Buchstaben von \(z\) liegen (beginnend bei dem ersten), d.h. in den ersten \(k\) \(a\)s. Beachtet man ferner, dass \(|v| \geq 1\) gilt, so kann man bereits \(v \in \{a\}^+\) schlussfolgern. Genauer kann man sogar sagen, dass es ein \(j\) mit \(1 \leq j \leq k\) geben muss derart, dass \(v = a^j\) gilt.
Wir betrachten nun das Wort \(u v^2 w = uvvw\), dass nach der dritten Bedingung in \(L\) sein müsste. Es ist aber \(u v^2 w = uvvw = a^{k+j} b^k\) (man beachte, dass wir \(v = a^j\) ja nun zweimal hintereinander dort stehen haben) und damit ist \(u v^2 w \not\in L\), denn \(j > 1\) und damit haben wir nicht mehr gleiche viele \(a\)s wie \(b\)s. Da die dritte Eigenschaft des Pumping Lemmas aber verlangen würde, dass für jedes \(i \geq 0\) dann \(uv^iw \in L\) ist, haben wir einen Widerspruch. Die ursprüngliche Annahme muss also falsch sein und daher ist \(L\) nicht regulär.
Das notieren von \(v^i\) mit \(i \geq 0\) nennt man Pumpen. Wie die Wahl von \(z\) ist es wieder ein kreativer Prozess, auf ein gutes \(i\) zu kommen, wobei "gut" hier bedeutet ein \(i\) zu finden, das einen Widerspruch erlaubt, mit dem also \(uv^iw \not\in L\) gilt. Es ist manchmal nötig, mehrere Versuche zu unternehmen, bis man auf ein gutes \(z\) und ein gutes \(i\) kommt. Die \(i\) könnten zudem auch unterschiedlich sein, je nachdem welche Zerlegung von \(z\) man hat. Es könnte also sein, dass man die Zerlegung von \(z\) erst geeignet parametrisieren und dann eine Fallunterscheidung machen muss und für unterschiedliche Fälle unterschiedliche \(i\) benötigt. Wichtig ist nur, dass man stets zu einem Widerspruch kommt.
Wir betonen hier auch noch einmal, dass auch \(i = 0\) gesetzt werden darf. Auch das Wort \(uw\) muss also in \(L\) sein und man hat einen Widerspruch, falls dies nicht der Fall ist. Dies ist in machen Fällen die einzige Möglichkeit einen Widerspruch herzustellen, daher sollte man diesen Spezialfall in Erinnerung behalten.
Damit haben wir nun gezeigt, dass es tatsächlich Sprachen gibt, die nicht regulär sind! Wir betonen dies im folgenden Satz.
Satz 2.4.3
Es gibt Sprachen, die nicht regulär sind. Ein Beispiel ist die Sprache \(L := \{a^n b^n \mid n \in \mathbb{N}\}\). Es gibt keinen DFA, der \(L\) akzeptiert.Das Pumping Lemma hilft uns für Sprachen wie obige und auch für weitere zu zeigen, dass die Sprachen nicht regulär sind. Das Pumping Lemma macht also eine Aussage über eine Eigenschaft, die alle regulären Sprachen haben. Es wird dann aber benutzt, um gerade zu zeigen, dass eine Sprache nicht regulär ist.
Wir fassen noch einmal den Ablauf zusammen, wenn man für eine Sprache \(L\) mittels Nutzung des Pumping Lemmas zeigen will, dass \(L\) nicht regulär ist.
- Annehmen \(L\) wäre regulär
- Die Zahl aus dem Pumping Lemma benennen (z.B. \(k\)).
- Ein Wort \(z\) finden mit \(|z| \geq k\) und \(z \in L\).
- Dieses Wort muss gut gewählt sein, damit der nachfolgende Widerspruch gelingt. Hier muss man also u.U. experimentieren.
- Für alle Zerlegungen von \(z\) in \(uvw\) zeigen, dass sie
im Widerspruch zur ersten, zweiten oder dritten Bedingung sind.- Üblicherweise betrachtet man alle Zerlegungen, die die erste und zweite Bedingung erfüllen und zeigt, dass man dann einen Widerspruch zur dritten Bedingung erhält.
- Also: Alle Zerlegungen \(z = uvw\) mit \(|uv| \leq k\) und \(|v| \geq 1\) betrachten.
- Zeigen, dass man ein \(i\) findet mit \(u v^i w \not\in L\). (Dies kann auch \(i = 0\) sein!)
Wir wollen zum Abschluss noch ein zweites Beispiel betrachten und hier beim Beweis zügig vorgehen. Zur Erinnerung: \(w^{rev}\) ist gerade das Wort \(w\) von hinten nach vorne gelesen, also z.B. \(011^{rev} = 110\).
Satz 2.4.4
\(L := \{ w w^{rev} \mid w \in \{0,1\}^* \}\) ist nicht regulär.Beweis
Angenommen \(L\) wäre regular. Dann gilt das Pumping Lemma. Sei \(k\) die Zahl aus dem Pumping Lemma. Wir betrachten \(z = 0^k 1^k 1^k 0^k\). Es ist \(z \in L\) und \(|z| \geq k\). Sei \(z = uvw\) eine Zerlegung von \(z\) mit \(|uv| \leq k\) und \(|v| \geq 1\). Hieraus folgt \(v = 0^j\) für ein \(j\) mit \(1 \leq j \leq k\). Nun ist aber \(u v^0 w = 0^{k-j} 1^k 1^k 0^k\) nicht mehr in \(L\) im Widerspruch zum Pumping Lemma. Die Annahme ist daher falsch und \(L\) somit nicht regulär.Man beachte, dass der obige Beweis mit \(z = 0^k 0^k\) nicht gelungen wäre. Die Wahl des Wortes ist also wichtig.
Wir haben in diesem Abschnitt das Pumping Lemma kennengelernt. Dieses macht eine Aussage über die regulären Sprachen, d.h. alle regulären Sprachen haben die im Pumping Lemma beschriebenen Eigenschaften.
Genutzt wird das Pumping Lemma dann, um nachzuweisen, dass eine Sprache nicht regulär ist. Dazu wird gezeigt, dass eine Sprache gerade nicht die im Pumping Lemma beschriebenen Eigenschaften hat. Das Vorgehen ist dabei zu einem gewissen Teil stets gleich. Bei der Wahl des Wortes, das man zerlegen möchte, und bei der Betrachtung aller Zerlegungen und dem Erreichen des Widerspruches ist aber stets Kreativität erforderlich.