Fachkonzept - Endlicher Automat als Akzeptor
Der erkennende endliche Automat (Akzeptor)
Aufgabe eines Akzeptors
Ein Akzeptor ist ein endlicher Automat, der die Syntaxprüfung für eine formale Sprache durchführen kann. Er bekommt zu Beginn ein Wort auf sein Eingabeband geschrieben und kann am Ende entscheiden, ob das eingegebene Wort syntaktisch korrekt aufgebaut ist und demnach zur definierten Sprache gehört.
Die Menge aller Wörter, die der Automat akzeptiert bildet die Sprache des Akzeptors. Es ist also auch möglich, eine Sprache mit einem Akzeptor zu definieren!
to+r) hast du einen Akzeptor kennen gelernt, der für jedes Eingabewort entscheiden konnte, ob es ein syntaktisch korrekter Torjubel ist. Die Sprache des Akzeptors war somit die Sprache der Torjubel.
Elemente eines Akzeptors
Ein erkennender endlicher Automat bzw. ein Akzeptor ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:
- Die Zustandsmenge: eine nichtleere, endlichen Menge
Zvon Zuständen des Automaten. - Das Eingabealphabet: eine nichtleere, endlichen Menge
Evon Eingabesymbolen, aus denen Eingabeworte gebildet werden können. - Die Überführungsfunktion: eine Funktion, der Form f : Z x E -> Z, die jedem Paar aus aktuellem Zustand und Eingabe einen Folgezustand zuordnet. Die Überführungsfunktion wird entweder durch den Zustandsgraphen des Automaten oder durch eine Automatentafel definiert.
- Der Startzustand: ein ausgezeichnetes Element Z0 aus der Zustandsmenge.
- Die Endzustände: eine (in der Regel nicht-leere) Teilmenge Ze der Zustandsmenge.
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.
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 des Akzeptors. Es wurde noch kein Eingabesymbol eingelesen. Der "Lesekopf" befindet sich somit auf dem ersten Zeichen des Eingabeworts.
-
Schrittweises Verarbeiten der Eingabezeichen:
- Symbol am Lesekopf einlesen
- Lesekopf um eine Stelle nach rechts verschieben
- In den Folgezustand wechseln (in Abhängigkeit vom aktuellen Zustand und des eingelesenen Symbols)
- 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.
Vertiefung
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. Diese Unterscheidung spielt für die Spracherkennung hier jedoch keine Rolle.
Der Automat heißt endlich, weil seine Zustandsmenge endlich ist. Du kannst dem Automat nicht unendlich viele Zustände hinzufügen. Deshalb kann ein Akzeptor z.B. auch irgendwann nicht mehr "mitzählen", wie viele Zeichen schon eingelesen wurden.
Ein DEA als Akzeptor kann nur reguläre Sprachen erkennen. Allerdings gibt es für jede reguläre Sprache einen Akzeptor.
Somit lässt sich sagen: Die Klasse der regulären Sprachen und die Klasse der mit einem Akzeptor definierbaren Sprachen sind identisch.
Grundidee - Fachkonzept von Klaus
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.
Die Symbolfolgen 2.1.1 und 21 werden dagegen nicht akzeptiert.
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.