Fachkonzept - Endlicher Automat als Akzeptor
Endlicher Automat als Akzeptor
Ein Akzeptor ist ein endlicher Automat, der die Syntaxprüfung für eine formale Sprache durchführen kann.
Die Idee der Überprüfung besteht darin, eine Symbolfolge nur dann zu akzeptieren, wenn sie bei der Verarbeitung das System vom Anfangszustand in ganz bestimmte, vorher festgelegte Zustände
- man nennt sie Endzustände - überführt.
Ein endlicher (erkennender) Automat bzw. ein Akzeptor ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:
- einer nichtleeren, endlichen Menge
Zvon Zuständen - einer nichtleeren, endlichen Menge
Evon Eingabesymbolen - einer Überführungsfunktion f : Z x E -> Z, die jedem Paar aus aktuellem Zustand und Eingabe einen Folgezustand zuordnet
- einem ausgezeichneten Element z0 ∈ Z, dem Anfangszustand
- einer (in der Regel nicht-leeren) Menge ZE ⊆ Z von Endzuständen
Hierfür schreibt man auch kurz A = (Z, E, f, Z0, Ze).
to+r) besteht der Akzeptor entsprechend aus den folgenden Bestandteilen:
- Zustandsmenge Z = {Z0, Z1, Z2, Z3, Z4}
- Eingabealphabet E = {o,r,t}
- Startzustand Z0
- Endzustände Ze = {Z3}
- Überführungsfunktion: die folgenden Abbildungen zeigen beide Varianten zur Darstellung einer Überführungsfunktion: Die Automatentafel und den Zustandsgraphen. Als Beispiel ist die rot markierte Kante des Zustandsgraphen in der Automatentafel ebenfalls rot hinterlegt. Beide Varianten definieren dort (rot markiert) für die Überführungsfunktion an der Stelle Z=Z2 und E=t den Funktionswert Z4. Sprich: Wenn ich im Zustand Z2 ein t einlese, so gelange ich den in Zustand Z4.
Das hier beschriebene Automatenmodell wird auch als deterministischer endlicher Automat (DEA) bezeichnet:
- Der Automat heißt deterministisch, weil er für jeden Zustand und für jede Eingabe nur einen möglichen Folgezustand besitzt. Man kann auch Automaten konstruieren, bei denen von einem Zustand mehrere Übergänge mit dem selben Eingabezeichen abzweigen - dann würde man von einem nichtdeterministischen Automaten sprechen.
- Der Automat heißt endlich, weil seine Zustandsmenge endlich ist. Du kannst dem Automat nicht unendlich viele Zustände hinzufügen.
Arbeitsweise eines Akzeptors
Ein Akzeptor arbeitet nach fest vorgegebenen Schritten:
- Startkonfiguration: Der Akzeptor befindet sich zu Beginn im Startzustand Z0. Das zu prüfende Wort steht auf dem Eingabeband, der "Lesekopf" befindet sich auf dem ersten Zeichen des Eingabeworts.
-
Schrittweises Verarbeiten der Eingabezeichen:
- Symbol am Lesekopf einlesen
- In den Folgezustand wechseln (in Abhängigkeit vom aktuellen Zustand und des eingelesenen Symbols)
- Lesekopf um eine Stelle nach rechts verschieben
- Verarbeitungsende: der Akzeptor stoppt seine Arbeit, wenn das Eingabewort komplett abgearbeitet ist und kein Symbol mehr eingelesen werden kann. Der Lesekopf steht dann hinter dem letzten Eingabesymbol.
- Ergebnisermittlung: Befindet sich der Automat am Ende in einem Endzustand aus Ze, so gilt das Eingabewort als akzeptiert.
Endlicher Automat als Spracherkenner
Die Menge E der Eingabesymbole eines endlichen Automaten
A = (Z, E, f, z0, ZE)
kann als Alphabet einer Sprache aufgefasst werden.
Ein endlicher Automat A = (Z, E, f, z0, ZE) akzeptiert
ein Wort w über dem Alphabet E,
wenn der Automat bei der Verarbeitung von w mit der Überführungsfunktion f
vom Anfangszustand z0 in einen Endzustand aus ZE überführt wird.
Die Menge aller Wörter über dem Alphabet E, die vom Automaten
A = (Z, E, f, z0, ZE)
akzeptiert werden, nennt man Sprache des Automaten A. Man bezeichnet sie mit L(A).
Einen Zustand, aus dem kein Endzustand mehr erreicht werden kann, bezeichnet man auch als Trap-Zustand.
Das Wort toor gehört zur Sprache
Der Automat durchläuft die Zustände Z0 → Z1 → Z2 → Z2 → Z3. Nach dem letzten Zeichen befindet er sich in Z3. Dieser Zustand gehört zur Menge der Endzustände: Das Wort wird akzeptiert, also gilt toor ∈ L(A).
Das Wort tooto gehört nicht zur Sprache
Hier lautet die Zustandsfolge Z0 → Z1 → Z2 → Z2 → Z4 → Z4. Beim zweiten t wechselt der Automat von Z2 nach Z4. Auch nach dem letzten o bleibt er dort. Z4 ist kein akzeptierender Zustand. Das Wort wird nicht akzeptiert, also gilt tooto ∉ L(A).
Z4 ist ein Trap-Zustand, aus dem kein Endzustand mehr erreicht werden kann: Für jedes weitere Eingabesymbol bleibt der Automat in Z4.