Exkurs - Grenzen von endlichen Automaten
Klammerausdrücke
Wir betrachten die Sprache LKlammer der stark vereinfachten Klammerausdrücke, die folgende Wörter enthält:
(), (()), ((())), ... .
Zur Sprache LKlammer gehören also alle Klammerausdrücke, bei denen nach einer Folge öffnender Klammern genau so viele schließende Klammern folgen.
Die Sprache LKlammer wird oft auch etwas abstrahierend in der folgenden Form dargestellt:
Lab = {anbn | n = 1, 2, 3, ...}
Die öffnenden Klammern werden durch das Symbol a repräsentiert, die schließenden
Klammern durch das Symbol b. Entscheidend ist auch hier, dass die Anzahl der
schließenden Klammern genau der Anzahl der öffnenden Klammern entspricht.
Problem:
Gibt es einen endlichen Automaten A, der die Sprache Lab = {anbn | n = 1, 2, 3, ...} erkennt?
Versuche, einen solchen endlichen Automaten A zu konstruieren, scheitern an der Schwierigkeit,
die Anzahl der öffnenden Klammern im Automaten mitzuzählen
.
Es scheint, dass diese Schwierigkeit bei endlichen Automaten - die ja eine feste Anzahl von Zuständen haben -
unüberwindbar ist.
Die folgende Argumentation zeigt, dass das tatsächlich der Fall ist.
Wir benutzen dabei einen Beweis durch Widerspruch. Wir nehmen an, dass es einen Automaten A gibt,
der die Sprache Lab der Klammerausdrücke erkennt und führen diese Annahme dann
zu einem Widerspruch. Die Annahme muss folglich falsch sein.
Erkennen von Lab = {anbn | n = 1, 2, 3, ...}
Angenommen, es gibt einen endlichen Automaten A mit L(A) = Lab.
Dieser Automat A hat eine feste Anzahl Zustände, etwa m = 15 (die Zahl 15 ist hier willkürlich gewählt,
sie spielt für die Argumentation keine Rolle).
Wir wählen nun ein Wort w = akbk aus Lab = {anbn | n = 1, 2, 3, ...}
mit k > m, etwa k = 16.
Bei der Abarbeitung des Wortes w = akbk muss bereits bei der Verarbeitung der 16 a's mindestens ein Zustand z mindestens zweimal durchlaufen werden, denn es gibt mehr a's als Zustände.
Wir nehmen einmal an, dass der Zustand z mit dem dritten a und mit dem siebten a erreicht wird.
Für die folgende Argumentation ist nicht entscheidend, mit welchen a's man z erreicht, sondern
nur, dass z zweimal durchlaufen wird.
Es entsteht eine Schleife, die erst mit dem ersten b wieder verlassen wird.
Wie die 16 b's den Automaten in einen Endzustand bringen, ist für die Argumentation ohne Belang.
Eine mögliche Konstellation zeigt das folgende Bild:
Dem Bild kann man direkt entnehmen, dass neben w = a16b16 auch andere Wörter wie a4b16
(Schleife wurde nicht durchlaufen) oder auch a8b16 (Schleife wurde einmal durchlaufen) akzeptiert werden.
Der Automat akzeptiert folglich auch Wörter, die nicht zu Lab = {anbn | n = 1, 2, 3, ...}
gehören.
Das steht aber im Widerspruch zur Annahme, dass der Automat A die Sprache Lab = {anbn | n = 1, 2, 3, ...}
erkennt.
Da die Annahme, dass es einen endlichen Automaten gibt, der die Sprache Lab = {anbn | n = 1, 2, 3, ...} erkennt, zu einem Widerspruch führt, muss die Annahme falsch sein.
Satz:
Die Sprache Lab = {anbn | n = 1, 2, 3, ...} kann nicht von einem endlichen Automaten
erkannt werden. Sie ist also nicht regulär.
