[ Weiter ] [ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]
Deterministische Endliche Automaten (DEA)
Idee des akzeptierenden deterministischen endlichen Automaten
Ein endlicher Automat ist eine (abstrakte) Maschine zur zeichenweisen Erkennung von Wörtern einer regulären Sprache. Sie ist nach jedem Verarbeitungsschritt in genau einem Zustand. Bei jedem Schritt wird ein Zeichen gelesen und aufgrund des aktuellen Zustands und dem Lesezeichen in einen Nachfolgezustand gewechselt. Wenn kein Zeichen mehr zu lesen ist und die Maschine in einem Endzustand ist, gilt die gelesene Zeichenkette als akzeptiert. Wenn kein Übergang mit dem gelesenen Symbol möglich ist, gilt die zu verarbeitende Zeichenkette als nicht akzeptiert. Beim Einlesen des ersten Zeichens einer Zeichenkette ist der Automat immer im sogenannten Startzustand.
Definition 4.1.1 (DEA, deterministic finite state automaton).
Ein deterministischer endlicher Automat A = ⟨Φ,Σ,δ,S,F⟩ besteht aus
Hinweis
Die Übergangsfunktion δ bestimmt den Folgezustand, der ausgehend vom aktuellen Zustand beim Lesen eines einzelnen Zeichens erreicht wird.
Zustandübergangsdiagramm
Es stellt einen EA anschaulich als gerichteten Graphen dar.
Partielle Zustandübergangsdiagramme
Die Definition von δ als totale Funktion verlangt für alle Zustände und Zeichen aus Σ eine Kante. In
der Linguistik zeigt man oft nur Knoten und Kanten, die für das Akzeptieren einer Zeichenkette
relevant sind.
Fehlerzustand (error state) und Fehlerübergänge
Um ein partielles Übergangsdiagramm zu vervollständigen, füge einen Zustand EF dazu, und mache ihn zum Endknoten aller nicht-bestehenden Kanten.
Beispiel 4.1.4 (Direktes Einlesen von EA im PROLOG-Format).
Beispiel 4.1.5 (Anzeige von Informationen zum obersten EA auf dem Stack).
Nicht-deterministischer endlicher Automat (NEA)
Idee des akzeptierenden nicht-deterministischen endlichen Automaten
Im Gegensatz zum DEA kann ein NEA nach jedem Verarbeitungsschritt in mehr als einen aktuellen Zustand wechseln. Bei jedem Schritt wird ebenfalls ein Zeichen gelesen und aufgrund der möglichen aktuellen Zustände und dem Lesezeichen in die zulässigen Nachfolgezustände gewechselt.
Beispiel-Evaluation
Siehe Abb. ?? auf Seite ??.
Definition 4.1.6 (NEA, non-deterministic finite state automaton).
Ein nicht-deterministischer endlicher Automat A = ⟨Φ,Σ,δ,S,F⟩ unterscheidet sich von einem DEA nur in der Übergangsfunktion. Vom aktuellen Zustand kann man mit einem Zeichen zu beliebig vielen Folgezuständen übergehen.
Beispiel 4.1.7 (Tabellendarstellung und Zustandsdiagramm).
δ | a | b |
s0 | {s1,fs2} | {fs2} |
s1 | ∅ | {fs2} |
fs2 | ∅ | ∅ |
Idee des akzeptierenden nicht-deterministischen endlichen Automaten mit 𝜖
Bei jedem Schritt wird wie beim NEA ein Zeichen gelesen und aufgrund der möglichen aktuellen Zustände und dem Lesezeichen in die zulässigen Nachfolgezustände gewechselt.
Die aktuellen Zustände umfassen aber immer auch alle Zustände, welche durch beliebig viele 𝜖-Übergange verbunden sind.
Bei einem 𝜖-Übergang wird kein Zeichen gelesen.
Definition 4.1.8 (𝜖-NEA, non-deterministic finite state automaton).
Ein nicht-deterministischer endlicher Automat mit 𝜖-Übergängen A = ⟨Φ,Σ,δ,S,F⟩ unterscheidet sich von einem NEA nur in der Übergangsfunktion.
δ : Φ × (Σ ∪{𝜖}) → ℘(Φ)
QUIZ Leichtes QUIZ zu endlichen Automaten
[ Weiter ] [ Seitenbeginn ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]