Fachkonzept - Endlicher Automat als Akzeptor
Grundidee
Mit einem zustandsbasierten System kann man überprüfen, ob Symbolfolgen bestimmte vorgegebene Eigenschaften haben. So lässt sich mit dem in der Abbildung gezeigten System testen, ob eine Zeichenfolge aus Ziffern und Punkten eine Python-Gleitkommazahl ohne Exponenten darstellt.
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.
Im dargestellten zustandsbasierten System werden z.B. die Symbolfolgen 21.1 und .21 akzeptiert,
nicht dagegen die Symbolfolgen 2.1.1 und 21.
Zustandsbasierte Systeme, die auf diese Weise Symbolfolgen verarbeiten, werden endliche (erkennende) Automaten oder Akzeptoren genannt.
Präzisierung
Wir betrachten den oben dargestellten endlichen Automaten zur Erkennung von Python-Gleitkommazahlen (ohne Exponenten).
Wesentlicher Bestandteil dieses Automaten ist die endliche Menge der Zustände:
Z = {q0, q1, q2, q3, q4, q5}
Der endliche Automat verarbeitet Symbole. Diese Symbole lassen sich zu einer endlichen Menge von Eingabesymbolen zusammenfassen:
E = {0, 1, 2, .}
Die Verarbeitungslogik besteht darin, dass die Verarbeitung eines Symbols den Automaten von einem aktuellen Zustand in einen neuen Zustand überführt. Diese Verarbeitungslogik kann mit einem Graphen (wie oben) oder mit einer Automatentafel beschrieben werden.
| 0 | 1 | 2 | . | |
|---|---|---|---|---|
| q0 | q1 | q1 | q1 | q4 |
| q1 | q1 | q1 | q1 | q2 |
| q2 | q3 | q3 | q3 | q5 |
| q3 | q3 | q3 | q3 | q5 |
| q4 | q3 | q3 | q3 | q5 |
| q5 | q5 | q5 | q5 | q5 |
Formal lässt sich eine solche Automatentafel als Überführungsfunktion deuten, die jedem Paar aus aktuellem Zustand und Eingabesymbol einen Folgezustand zuordnet.
f: Z x E -> Z mit f(q0, 0) = q1, f(q0, 1) = q1, ...
Jede Verabeitung einer Symbolfolge beginnt in einem ausgezeichneten Anfangszustand:
z0 = q0
Für die Erkennung der zu akzeptierenden Symbolfolgen wird schließlich eine Menge von Endzuständen benötigt:
ZE = {q2, q3}
Das Verarbeitungsmodell "endlicher (erkennender) Automat" lässt sich demnach wie folgt abstrakt beschreiben:
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).
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).
Ein endlicher Automat ist also eine Verarbeitungseinheit, die Symbole eines Eingabeworts verarbeitet und sich dabei stets in einem bestimmten Zustand befindet. Anhand des Zustands am Ende der Verarbeitung kann dann festgestellt werden, ob das zu verarbeitende Eingabewort akzeptiert wird oder nicht.
Die Abbildung veranschaulicht eine solche Verarbeitungseinheit. Die Symbole des zu verarbeitenden Eingabeworts sind in einzelne Zellen eines Eingabebandes geschrieben. Bei der Berarbeitung des Eingabeworts werden die einzelnen Symbole des Worts mit einem Lesekopf erfasst. Abhängig vom jeweils gelesenen Symbol wird die eigentliche Verarbeitungseinheit in einen passenden Zustand versetzt. Die Verarbeitung endet, wenn der Lesekopf alle Symbole des Wortes erfasst hat. Befindet sich die Verarbeitungseinheit dann in einem Endzustand, so wird das Wort akzeptiert.