Fachkonzept - Kellerautomat
Die Grundidee
Die Grundidee soll anhand einer Verarbeitungseinheit erläutert werden, die
Klammerausdrücke der Gestalt (((...))) erkennen, bei denen nach einer Anzahl
öffnender Klammern genauso viele schließende Klammern folgen.
Die gezeigte Verarbeitungseinheit befindet sich stets in einem bestimmten Zustand, verarbeitet Symbole eines Eingabeworts und benutzt einen Stapel / Keller zum Zwischenspeichern von Zeichen(ketten).
Im vorliegenden Fall befindet sich die Verarbeitungseinheit zu Beginn in einem Anfangszustand q0.
In diesem Zustand werden die öffnenden Klammern verarbeitet, indem die Symbole auf den Stapel gelegt werden.
Beim Übergang zu den schließenden Klammern wechselt die Einheit den Zustand. Im neuen Zustand wird jeweils -
solange schließenden Klammern als Symbole verarbeitet werden und der Stapel nicht leer ist -
das oberste Stapelelement entfernt. Wenn auf diese Weise das gesamte Eingabewort verarbeitet werden kann und
der Stapel am Ende wieder leer ist, wechselt die Verarbeitungseinheit in einen Endzustand und das
Eingabewort gilt als akzeptiert.
Präzisierung
Zur Präzisierung betrachten wir zunächst das folgende Zustandsdiagramm, das einen sogenannten Kellerautomaten festlegt.
Der Kellerautomat hat eine nichtleere endliche Menge Z von Zuständen. Im vorliegenden Fall ist das die Menge
Z = {q0, q1, q2}. Der Zustand q0 ist hier als Anfangszustand ausgezeichnet,
der Zustand q2 als ein Endzustand.
Eine Verarbeitung wird durch einen Zustandsübergang (von einem Zustand in einen anderen - gegebenenfalls denselben Zustand) beschrieben. Ein Zustandsübergang erfolgt nur in Abhängigkeit von einem Eingabesymbol und den obersten Kellersymbolen. Ein Zustandsübergang aktualisiert zudem den Keller, indem Symbole vom Keller entfernt und neue Symbole im Keller abgelegt werden. Im Zustandsdiagramm werden diese Informationstripel in der Gestalt (Eingabe, zu entfernende oberste Kellersymbole; hinzuzufügende oberste Kellersymbole) an die Übergangspfeile geschrieben. Die Bedeutung dieser Informationstripel soll anhand konkreter Beispiele weiter erläutert werden.
Das Tripel (,(;(( bedeutet: Wenn die Eingabe ( vorliegt und im Keller oben
das Kellersymbol ( liegt, dann entferne dieses oberste Kellersymbol
und lege die Symbole des Worts (( der Reihe nach in den Keller.
Das Tripel ),(;λ bedeutet: Wenn die Eingabe ) vorliegt und im Keller oben
das Kellersymbol ( liegt, dann entferne dieses oberste Kellersymbol
und lege die Symbole des leeren Worts - also nichts - in den Keller.
Das Tripel (,Z;(Z bedeutet: Wenn die Eingabe ( vorliegt und im Keller oben
das Kellersymbol Z liegt, dann entferne dieses oberste Kellersymbol
und lege die Symbole des Wort (Z der Reihe nach in den Keller. Beachte, dass Z hier ein
zusätzliches Kellersymbol ist, das einen leeren Keller beschreibt.
Das Tripel λ,Z;λ bedeutet: Wenn die Eingabe λ vorliegt - wenn also
keine Eingabesymbole mehr vorhanden sind - und im Keller oben
das Kellersymbol Z liegt - wenn der Keller also leer ist -, dann entferne dieses oberste Kellersymbol
und lege die Symbole des leeren Worts - also nichts - in den Keller.
Der Kellerautomat verarbeitet also die Eingabesymbole ( und ).
Der Kellerautomat benutzt zudem die Symbole ( und Z zum Zwischenspeichern im Keller.
Zusammenfassend lässt sich das Verarbeitungsmodell Kellerautomat
wie folgt charakterisieren.
Ein (deterministischer) Kellerautomat ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:
- eine nichtleere, endliche Menge von Zuständen
- eine nichtleere, endliche Menge von Eingabesymbolen
- eine nichtleere, endliche Menge von Kellersymbolen,
- eine Überführungsfunktion, die dem aktuellem Zustand in Abhängigkeit von einer vorgegebener Eingabe (die auch das leere Wort sein kann) und einer (evtl. leeren) Folge von Kellersymbolen die Folgezustände zuordnet und zudem die jeweils neu im Keller aufzunehmenden Symbole festlegt,
- ein ausgezeichneter Zustand - dem Anfangszustand -,
- eine Menge von Endzuständen
- ein ausgezeichnetes Kellersymbol, das die untere Kellerbegrenzung beschreibt.
Bei einem nichtdeterministischer Kellerautomaten
müssen die Zustandsübergänge nicht eindeutig sein. Zudem sind λ-Übergänge
der Gestalt λ,λ;λ erlaubt.
Ein Kellerautomat ist also eine Verarbeitungseinheit, die Symbole eines Eingabeworts verarbeitet, sich dabei stets in einem bestimmten Zustand befindet und die zum Zwischenspeichern von Symbolen einen Stapel / Keller benutzt.
Spracherkennung mit Kellerautomaten
Die Menge der Eingabesymbole eines Kellerautomaten kann als Alphabet einer Sprache aufgefasst werden.
Unter der Sprache eines Kellerautomaten versteht man die Menge aller Wörter aus Eingabesymbolen, die den Kellerautomaten vom Anfangszustand in einen Endzustand überführen.
Wenn K ein gegebener Kellerautomat ist,
dann schreiben wir L(K) für die Sprache des Kellerautomaten K.