Gesucht ist zum Ausdruck a = anbn mit n Î N0 ein erkennender Automat.
Offensichtlich ist der folgende Automat unbrauchbar:
Er stellt den regulären Ausdruck a = a*b*
dar, d.h. eine beliebige Anzahl a gefolgt von einer nicht notwendigerweise
gleichen beliebigen Anzahl b. Im ursprünglichen Ausdruck muss aber die Anzahl
der a und der nachfolgenden b gleich groß sein, also z.B. ab, aabb, aaabbb,
aaaabbbb usw.
Der zugehörige Automat müsste sich etwa so aufbauen:
Dies ist aber kein endlicher Automat. Daher kann die Sprache dieses regulären
Ausdrucks mit den bisherigen endlichen Automaten nicht erkannt werden. Dies liegt
daran, dass ein endlicher Automat nicht beliebig viele Zustände haben kann.
Man muss einen Automaten konstruieren, der die bisherige Verarbeitung eines Wortes in einem gewissen Umfang speichern kann. Im Beispiel muss der Automat "wissen" wieviele 'a' vorkamen, wenn das erste 'b' auftritt. Dies leistet ein Kellerautomat.
Ein Kellerautomat verfügt neben der Eingabe und inneren Zuständen
zusätzlich über einen Kellerspeicher. In diesem kann er das oberste
Zeichen durch eine Zeichenfolge aus einem Kelleralphabet K ersetzen.
Der Kellerspeicher oder Keller erlaubt also immer nur den Zugriff auf das
oberste, d.h. zuletzt abgelegte Zeichen. Er funktioniert nach dem Prinzip
LIFO
(last input, first
output). Anfangs enthält der Keller nur das Startsymbol
k0 Î K, d.h. der
Keller ist leer.
Die Bearbeitung einer Eingabe stoppt, wenn das Eingabewort vollständig
bearbeitet ist. Befindet sich der Automat in einem Endzustand, unabhängig
vom Zustand des Kellers, so wird das Eingabewort akzeptiert.
Arbeitsweise des Kellerautomaten
Mit dem Kellerautomaten lässt sich obige Aufgabe, die Erkennung der Sprache zum Ausdruck a = anbn lösen: Zur Lösung.
Der Kellerautomat ist eine Erweiterung der endlichen Automaten, denn benutzt man den Keller nicht, so stimmt die Sprache des Kellerautomaten mit der des entsprechenden endlichen Automaten überein, wenn man dieselben Zustände verwendet und die Übergange (s,e,k0) -> (s',k0) ersetzt durch (s,e) -> s'. Umgekehrt kann man jeden endlichen Automaten durch einen Kellerautomaten ersetzen, der dieselbe Sprache erkennt.
Autor: Jürgen Dehmer
Letzte Änderung: