Es soll ein Akzeptor gesucht werden, der Worte der Form a^{n}n^{n} mit n \in \mathbb{N} erkennen kann. Solche Worte sind für die Syntax von Programmiersprachen von großer Bedeutung, weil sie die einfachste mögliche Klammerstruktur darstellen. Wir denken dabei an arithmetische Ausdrücke mit den Klammern „(“ und „)“ oder an Verbundanweisungen mit den Klammern BEGIN und END oder an Repeat Anweisungen mit den Klammern REPEAT und UNTIL.
Nach der Art der zugelassenen Regeln (linkslinear oder abschließend) müssen wir aus dem Startzeichen erst die bn erzeugen, dann links davon die an. Dies geht nur mit einem Rekursionsmechanismus. Die einfachste Regel dazu wäre etwa (B, Bb) bzw. (A, Aa). Wir haben dazu nur endlich viele Regeln zur Auswahl, sollen aber beliebig viele b bzw. a erzeugen. Dies geht nur, wenn es gewisse Zyklen der Anwendung von Regeln gibt. Damit kann man dann aber auch zeigen, dass nicht nur Worte mit gleich vielen a’s und b’s zu einer solchen Sprache gehören. Dies wird in der nebenstehenden Grafik verdeutlicht.
Zu jedem n \in \mathbb{N} gibt es einen anderen erkennenden Automaten; wir suchen jedoch einen einzigen Automaten, d. h. einen, bei dem die Anzahl der a’s nicht beschränkt ist. Dass dies mit einem Automaten, der nur endlich viele Zustände besitzt, nicht geht, leuchtet unmittelbar ein. Einem solchen Automaten fehlt eine wichtige Eigenschaft: er kann nicht zählen (eine Zahl oder Menge nicht speichern).
Wenn die Sprache eines endlichen Automaten Wörter der Form anbn für beliebig große natürliche Zahlen n enthält, dann auch Wörter der Gestalt ambn mit n \neq m.
Beim Lesen der a’s muss der Automat einen Kreis im Zustandsgraphen durchlaufen, wenn er für beliebige Zahlen n anbn erkennen soll. Der Beweis soll an dieser Stelle nicht geführt werden. Diese Sprache ist nicht regulär und kann damit nicht von einem endlichen Automaten erkannt werden.
Zusammenfassung: Nur Sprachen, die keine beliebig tief verschachtelten Strukturen enthalten, können von endlichen Automaten erkannt werden.
- Bereits die Analyse arithmetischer Terme, insbesondere verschachtelter Klammern, übersteigt die Fähigkeiten endlicher Automaten.
- Die Beschränkung der Fähigkeiten endlicher Automaten liegt – ungenau ausgedrückt – daran, dass sie wegen der endlichen Anzahl ihrer Zustände (ihrem „Gedächtnis“) nicht beliebig weit zählen können.
