Endliche Automaten
Umgangssprachlich verwendet man den Begriff „Automat“ für technische Geräte, die zu gewissen Eingaben nach einem schematischen (algorithmischen) Verfahren nach endlich vielen Schritten erwartete Ausgaben liefern. Wir kennen Fahrscheinautomaten und Getränkeautomaten.
In der Informatik verstehen wir unter Automaten etwas anderes. Endliche Automaten sind das einfachste Berechnungsmodell, welches hier betrachtet wird. Endliche Automaten entsprechen Programmen, die gewisse Entscheidungsprobleme lösen und dabei keine Variablen verwenden.
Endliche Automaten sind Akzeptoren
Abstrakte Automaten dienen zur Definition formaler Sprachen, indem sie vorgegebene Wörter als Elemente einer bestimmten Sprache akzeptieren oder ablehnen. Sie werden daher auch Akzeptoren genannt.
Definition
Schauen wir uns nun an, wie ein Automat formal betrachtet wird:
Ein endlicher Automat ein 5-Tupel folgender Zusammensetzung: \(A = (Q, \sum, q_0, \delta, F)\).
- Die endliche Zustandsmenge \(Q\)
- Das endliche Eingabealphabet \(\sum\)
- Der Startzustand \(q_0 \in Q\)
- Die Übergangsfunktion \(\delta: Q \times \sum \rightarrow Q\)
- Die Endzustandsmenge \(F ⊆ Q\)
Anwendungsgebiete
In der Informatik finden endliche Automaten in der Spracherkennung Anwendung. Anhand der erreichten Zustände des Automaten soll erkannt werden, ob eine Symbolfolge (ein Wort) zu einer Sprache gehört oder nicht.
Solch zustandsbasierte Systeme die auf diese Weise eine Symbolfolge verarbeiten, nennt man endliche Automaten.
Durch die Verarbeitung eines Symbols wird der Automat von einem aktuellen in einen neuen Zustand überführt. Diese Verarbeitungslogik kann dabei z. B. als Graph dargestellt werden, wie sie auch im Beispiel abgebildet ist.
Ein Automat entsprechend dieser Definition nennt man auch Deterministisch Endlicher Automat (DEA). Dieser zeichnet sich dadurch aus, dass ausgehend von einem Zustand mit einem bestimmten Eingabesymbol nur ein anderer Zustand erreicht werden kann.