Ein endlicher Automat ist ein Modell eines Systems mit Ein- und Ausgaben, welches auf Basis einer endlichen Anzahl von möglichen (internen) Konfigurationen, sog. "Zustände" arbeitet, bestimmte Eingabewörter akzeptiert und, falls festgelegt, entsprechende Ausgabewörter produziert.
(Formale) Definition:
Ein endlicher Automat ist ein Sechstupel A = (I, O, Q, δ, q0, F), wobei
- I ist das Eingabealphabet (alle gültigen Eingabezeichen, die der Automat kennt),
- O ist das Ausgabealphabet (analog zu I),
- Q ist eine endliche, nichtleere Menge von Zuständen,
- q0 ∈ Q der Startzustand,
- δ: Q x I → Q x O die Zustandsübergangsfunktion mit einer Abbildung der Paare (q, i), wobei q ∈ Q ein Zustand ist und i ∈ I ein Eingabezeichen in ein Paar (q', o), wobei q' ∈ Q ein Folgezustand und o ∈ O ein Ausgabezeichen ist sowie
- F ⊆; Q der Menge der Endzustände.
Der hier definierte endl. Automat ist deterministisch, d.h. zu jedem Zustand existiert genau ein Folgezustand. Neben diesen existieren noch nichtdeterministische Automaten, die in Potenzmenge über die Paare der Folgepaare abbilden. Somit existieren Zustände mit mehreren Folgezuständen zwischen denen der Automat nichtdeterministisch auswählt. Diese lassen sich allerdings in einen äquivalenten deterministischen Automaten mit Hilfe der Potenzmengenkonstruktion umwandeln.
|
Glossar 
Forschungsprojekte 
Anbieterverzeichnis 
Datenbanksuche 
Highlights 
Eintrag kommentieren
