Exkurs - Grenzen von endlichen Automaten

Klammerausdrücke

Wir betrachten die Sprache L_Klammer der stark vereinfachten Klammerausdrücke, die folgende Wörter enthält:

(), (()), ((())), ... .

Zur Sprache L_Klammer gehören also alle Klammerausdrücke, bei denen nach einer Folge öffnender Klammern genau so viele schließende Klammern folgen.

Die Sprache L_Klammer 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 L_ab = {aⁿbⁿ | 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 L_ab der Klammerausdrücke erkennt und führen diese Annahme dann zu einem Widerspruch. Die Annahme muss folglich falsch sein.

Erkennen von L_ab = {aⁿbⁿ | n = 1, 2, 3, ...}

Angenommen, es gibt einen endlichen Automaten A mit L(A) = L_ab. 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 = a^kb^k aus L_ab = {aⁿbⁿ | n = 1, 2, 3, ...} mit k > m, etwa k = 16. Bei der Abarbeitung des Wortes w = a^kb^k 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 = a¹⁶b¹⁶ auch andere Wörter wie a⁴b¹⁶

(Schleife wurde nicht durchlaufen) oder auch a⁸b¹⁶ (Schleife wurde einmal durchlaufen) akzeptiert werden.

Der Automat akzeptiert folglich auch Wörter, die nicht zu L_ab = {aⁿbⁿ | n = 1, 2, 3, ...} gehören. Das steht aber im Widerspruch zur Annahme, dass der Automat A die Sprache L_ab = {aⁿbⁿ | n = 1, 2, 3, ...} erkennt.

Da die Annahme, dass es einen endlichen Automaten gibt, der die Sprache L_ab = {aⁿbⁿ | n = 1, 2, 3, ...} erkennt, zu einem Widerspruch führt, muss die Annahme falsch sein.