Endlicher Automat

Abstrakte Maschine mit endlich vielen Zuständen. Sie liest ein Wort Symbol für Symbol, wechselt dabei den Zustand und akzeptiert das Wort, wenn sie am Ende in einem Endzustand steht. Endliche Automaten erkennen genau die regulären Sprachen.

Deterministischer endlicher Automat (DFA)

A = (Σ, S, δ, s₀, F) mit Eingabealphabet Σ, Zustandsmenge S, Überführungsfunktion δ, Startzustand s₀ und Endzuständen F (Quelle - Automatentheorie Zusammenfassung).

• Deterministisch: Zu Zustand und Symbol gibt es höchstens einen Folgezustand.
• Akzeptierte Sprache L(A): alle Wörter, die von (s₀, w) in eine Endkonfiguration (s ∈ F, ε) führen. Bricht der Automat ab oder endet er ausserhalb von F, wird das Wort abgelehnt.
• Vollständig (total): Fehlende Übergänge werden auf einen zusätzlichen toten Zustand gelenkt, der sich selbst nie mehr verlässt. Jeder DFA lässt sich so vervollständigen.
• Darstellungen: Zustandsgraph, Zustandstafel, Mengendarstellung von δ als Tripel (Zustand, Symbol, Folgezustand).

Varianten, alle gleich mächtig

Es gilt DFA = NFA = ε-FA = GFA = REG (Quelle - Automatentheorie Zusammenfassung).

Minimierung

Zu jedem endlichen Automaten gibt es einen minimalen äquivalenten Automaten, der bis auf die Benennung der Zustände eindeutig ist (alle minimalen Automaten sind isomorph). Verfahren (Zerlegungsverfeinerung, Beispiel S. 10–11):

1. Erste Zerlegung Π₁: Endzustände gegen Nicht-Endzustände.
2. Für jeden Block prüfen, ob alle Zustände bei jeder Eingabe in denselben Block führen. Wenn nicht, wird der Block entsprechend aufgeteilt, und es entsteht eine feinere Zerlegung Πᵢ₊₁.
3. Wiederholen, bis Πᵢ₊₁ = Πᵢ. Die Blöcke sind die Zustände von A_min.

Beispiel der Quelle: Zustände s₀–s₄, Endzustand s₄ (über 0,1 stabil). Π₁ = {{s₄}, {s₀,s₁,s₂,s₃}}. Bei Eingabe 0 führen s₁ und s₃ nach {s₄}, s₀ und s₂ nicht, also Π₂ = {{s₄}, {s₀,s₂}, {s₁,s₃}}. Π₃ = Π₂, Ende. Der minimale Automat hat 3 statt 5 Zustände ({s₀,s₂} → 0 → {s₁,s₃} → 0 → {s₄}, bei 1 jeweils zurück zu {s₀,s₂}) und akzeptiert dieselbe Sprache, nämlich alle Wörter, die „00“ enthalten.

Automaten mit Ausgabe

• Mealy-Maschine: Die Ausgabe hängt von Zustand und Eingabe ab, gesteuert über den Übergang. Sie berechnet eine Funktion von Wörtern auf Wörter („Mealy-berechenbar“).
• Moore-Maschine: Die Ausgabe hängt nur vom erreichten Zustand ab. Weil schon der Startzustand eine Ausgabe erzeugt, ist die Ausgabe ein Zeichen länger als die Eingabe.

Anwendungen

• Pattern-Matching in der Textverarbeitung: Zu einem Suchwort v wird ein Automat A_v gebaut. Bei einem Fehlschlag springt er in den Zustand, der dem längsten Suffix des bisher Gelesenen entspricht, das zugleich Präfix von v ist. Das ist das Prinzip hinter dem Knuth-Morris-Pratt-Algorithmus.
• Zustandsmodellierung in der Systemprogrammierung, dynamische Modelle in der objektorientierten Entwicklung (Zustandsdiagramme), Mensch-Computer-Dialoge (Quelle - Automatentheorie Zusammenfassung)
• Scanner (lexikalische Analyse) → Reguläre Sprache

Grenze

Ein endlicher Automat hat nur endlichen Speicher und kann deshalb nicht zählen. Die Sprache aⁿbⁿ erkennt er nicht. Dafür braucht es einen Keller → Kontextfreie Sprache.

Beispiele aus der Quelle

• NFA, parallel abgearbeitet (S. 5): Der Automat bleibt mit 0 und 1 in s₀ und kann mit 0, 1, 1 über s₁, s₂ nach s₃ (Endzustand). Er akzeptiert also alle Wörter, die auf 011 enden. Für 1100011 wird die Folge der Zustandsmengen berechnet: {s₀} → … → {s₀,s₁} → {s₀,s₁,s₂} → {s₀,s₂,s₃} → {s₀,s₃}. Weil die Endmenge s₃ enthält, wird das Wort akzeptiert: Es genügt eine akzeptierende Konfigurationsfolge (Quelle - Automatentheorie Zusammenfassung).
• ε-Regeln eliminieren (S. 8–9), in vier Schritten:
  1. Neuer Startzustand mit ε-Übergang zu allen bisherigen Startzuständen, neuer Endzustand f mit ε-Übergängen von allen bisherigen Endzuständen.
  2. ε-Zyklen eliminieren (die Zustände darauf verschmelzen).
  3. Für jede Folge „ε, dann a“ einen direkten a-Übergang einfügen.
  4. Endzustände bestimmen und restliche ε-Übergänge entfernen.
• GFA: Ein Übergang s₀ –abba→ s₅ liest ein ganzes Wort auf einmal.
• Komplement bilden (S. 17, handgezeichnet): 1. Automat total machen, d.h. einen toten Zustand ergänzen, in den alle fehlenden Übergänge führen. 2. End- und Nicht-Endzustände vertauschen. Ohne Schritt 1 würden Wörter, bei denen der Automat abbricht, fälschlich weiter abgelehnt.
• Elementare Automaten (S. 14): A = (Σ, {s₀}, ∅, s₀, ∅) akzeptiert die leere Sprache, mit F = {s₀} die Sprache {ε}, und mit einem Übergang s₀ –a→ s₁ (s₁ Endzustand) die Sprache {a}. Daraus setzt ein Scanner-Generator den Automaten für einen regulären Ausdruck zusammen (Reguläre Sprache).

Verwandt

• Reguläre Sprache – die von endlichen Automaten erkannte Sprachklasse
• Formale Sprache – Grundbegriffe
• Chomsky-Hierarchie – Einordnung (Typ 3)
• Turingmaschine – das mächtigste Automatenmodell
• Kellerautomat – erweitert den endlichen Automaten um einen Stack
• Boolesche Algebra – Schaltlogik, aus der Schaltwerke (Mealy/Moore) gebaut werden