|
Der EA ist ein sehr beschränkter Automat zur Worterkennung.
Das Eingabeband kann nur gelesen werden.
Das Eingabewort wird dabei Zeichen für Zeichen gelesen, Rücksprünge sind nicht möglich.
Die Anzahl der Zustände ist klein und endlich.
Die Endzustände bilden eine Teilmenge der Zustände.
Erreicht der Automat einen Endzustand nach der vollständigen Bearbeitung des Eingabewortes, so hält er akzeptierend an.
Ist er am Wortende nicht in einem Endzustand angekommen, so akzeptiert er das Eingabewort nicht.
Die Kontrolleinheit besitzt das Wissen über Zustandsübergänge.
Anhand des gerade eingelesenen Zeichen und des aktuellen Zustandes erkennt sie den Folgezustand (falls vorhanden), in den gewechselt werden muss.
Beim Wechsel von einem Zustand in den nächsten wird ein Eingabezeichen konsumiert, d.h. der Lesekopf um eine Position verschoben.
Eine Ausnahme bilden die "ε-Übergänge".
Bei diesen erfolgt der Übergang von einem Zustand in den Folgezustand ohne Verschieben des Lesekopfes und damit ohne eine Eingabezeichen zu lesen.
Die Arbeitsweise von EAs kann sehr gut durch einen Graphen beschrieben werden.
Dabei bilden die Knoten die Zustände.
Die Kanten sind die möglichen Übergänge zwischen zwei Zuständen.
Die Kantenbeschriftung gibt das konsumierte Eingabezeichen an.
EAs im Parsingprozess
EA können effizient erkennen, ob ein Eingabewort in der von ihnen akzeptierten Sprache liegt.
Für einen EA ohne ε-Übergänge entspricht die dafür benötigte Schrittzahl der Länge des Wortes.
Eine Fehlererkennung erfolgt u.U. schon früher (Eintritt in absorbierenden Zustand1, keine Folgekonfiguration vorhanden).
Die einfache Struktur endlicher Automaten (z.B. in der Graphendarstellung) zeigt jedoch bereits die Grenzen der Sprachen auf,
die von EAs akzeptiert werden können.
_____
1 In einen absorbierenden Zustand (kein Endzustand!) führen Übergänge zwar hinein, aber nicht wieder hinaus.
Die Analyse bleibt dort quasi "gefangen".
| 
1
2
3
4
5
6
Kellerautomaten