Deterministischer endlicher automat

Deterministischer endlicher automat

Ein deterministischer endlicher Automat (DEA, engl.: DFA=deterministic finite automaton) ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (mögliche Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt.

Formal kann ein DEA \mathcal{A} als 5-Tupel \left( Q, \Sigma, \delta, q_0, F \right) definiert werden. Hierbei gilt Folgendes:

  • Q (oft auch Z oder S) ist eine Zustandsmenge, eine nichtleere endliche Menge von Zuständen. Zum Beispiel z0, z1 und z2 oder auch „Getränkeautomat wartet auf Eingabe“, „Kaffee ausschenken“, „Wechselgeld zurückgeben“, …
  • Σ ist ein endliches Eingabealphabet, also erlaubte Eingaben, wie z. B. 1 und 0 oder auch „Münze einwerfen“, „Taste für Milchkaffee drücken“, „Taste Abbruch drücken“, …
  • Es gibt eine Übergangsfunktion \delta : Q \times \Sigma \rightarrow Q, so dass für p, q \in Q und a \in \Sigma gilt δ(q,a) = p. δ ordnet jedem Paar, bestehend aus einem Zustand q und einem Eingabesymbol a, einen neuen Zustand p zu. Der Automat wechselt also von einem Zustand q in einen anderen Zustand p, wenn im Zustand q eine (gültige) Eingabe a gemacht wurde. Beispiel: δ(z0, 1) = z2 oder δ(„Getränkeautomat wartet auf Eingabe“, „Taste für Milchkaffe gedrückt“) = "Kaffee ausschenken"
  • q_0 \in Q ist der Startzustand. Statt q0 wird oft auch z0 verwendet. Beispiel: z0 oder „Getränkeautomat wartet auf Eingabe“.
  • F \subseteq Q (oft auch A) ist die Menge der akzeptierenden Zustände, die sogenannten Finalzustände. Zum Beispiel: z2 oder „Getränkeautomat wartet auf Eingabe“ (in diesem Fall ist der Startzustand auch ein Finalzustand)

Wenn sich der Automat nach dem Lesen des Eingabewortes w \in \Sigma^*, also einer Folge von Eingaben und den damit verbundenen Zustandsübergängen, in einem Finalzustand aus F befindet, so gehört w zur Sprache L\left(A\right).

Ist ein DEA in der Lage jedes Wort über dem betrachteten Alphabet bis zum Ende lesen zu können, auch wenn es nicht in der zu akzeptierenden Sprache enthalten ist, wird er vollständig genannt.

Nichtdeterministische endliche Automaten (NEAs), DEAs und Typ-3-Grammatiken (vgl. Chomsky-Hierarchie) beschreiben die gleiche Sprachklasse. NEAs lassen sich mittels Potenzmengenkonstruktion in äquivalente DEAs wandeln.

Minimierung

Zu jedem DEA existiert ein (bis auf die Benennung der Zustände) eindeutiger minimaler Automat, der dieselbe Sprache akzeptiert.

Da die Zustände des Minimalautomaten den Äquivalenzklassen der vom endlichen Automaten M akzeptierten Sprache unter der Nerode-Relation entsprechen, spricht man auch vom Äquivalenzklassenautomat:

u \sim_{L(M)} v \Longleftrightarrow (\forall w \in \Sigma^{*} : uw \in L(M) \Leftrightarrow vw \in L(M))

Sei M = (Q,Σ,δ,q0,F) ein deterministischer endlicher Automat. Dann ist N = (Q',Σ,δ',q0',F') mit

  • Q' = \Big\{[w]_{L(M)}  \mid w \in \Sigma^*\Big\}
  • ~q'_0 = [\epsilon]_{L(M)}
  • ~\delta'([u]_{L(M)} ,a)=[ua]_{L(M)}
  • F' = \Big\{[u]_{L(M)}  \mid u \in L(M)\Big\}

der Äquivalenzklassenautomat zu M.

Die Minimierung eines deterministischen Automaten kann algorithmisch durch fortwährende Verfeinerung der Äquivalenzklassen gelöst werden. Man beginnt mit den Zustandsmengen F und QF. Für jeden Buchstaben aus dem Alphabet wird nun jede Zustandsmenge dahingehend aufgeteilt, dass die Überführungsfunktion die Zustände jeder neuen Menge den Buchstaben in eine jeweils eindeutige Menge abbildet. Dies wird so oft wiederholt bis sich keine Änderung mehr ergibt.

Siehe auch

Literatur

  • John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage. Pearson Studium, Reading 2002, ISBN 3-8273-7020-5
  • Gottfried Vossen, Kurt-Ulrich Witt, Grundkurs Theoretische Informatik 3.Auflage, ISBN 3-528-23147-5
  • Peter Sander, Wolffried Stucky, Rudolf Herschel: Automaten, Sprachen, Berechenbarkeit. Teubner, Stuttgart 1992, ISBN 3-519-02937-5
  • Uwe Schöning: Ideen der Informatik, Grundlegende Modelle und Konzepte. Oldenbourg, München 2006, ISBN 3-486-57833-2

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Deterministischer endlicher Automat — Ein deterministischer endlicher Automat (DEA, engl.: deterministic finite state machine oder deterministic finite automaton (DFA)) ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von… …   Deutsch Wikipedia

  • Nicht-deterministischer endlicher Automat — Ein nichtdeterministischer endlicher Automat (NEA, engl: NFA=nondeterministic finite automaton) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere Möglichkeiten gibt. Formal kann ein NEA als 5 Tupel definiert werden. Hierbei… …   Deutsch Wikipedia

  • Endlicher Automat — Abb. 1: Beispiel eines EA der eine Tür beschreibt Ein endlicher Automat (EA, auch Zustandsmaschine, englisch finite state machine (FSM)) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt… …   Deutsch Wikipedia

  • Automat (Informatik) — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Moore Automat — Ein Moore Automat (benannt nach dem Mathematiker Edward F. Moore (1925 2003)) ist ein endlicher Automat, welcher deterministisch oder nichtdeterministisch sein kann. Im Gegensatz zum Mealy Automaten hängt seine Ausgabe ausschließlich von seinem… …   Deutsch Wikipedia

  • Mealy Automat — Ein Mealy Automat ist ein endlicher Automat, dessen Ausgabe (im Gegensatz zu einem Moore Automat) von seinem Zustand und seiner Eingabe abhängt. Anschaulich bedeutet das, dass jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet wird. Der… …   Deutsch Wikipedia

  • Moore-Automat — Ein Moore Automat (benannt nach dem Mathematiker Edward F. Moore (1925 2003)) ist ein endlicher Automat, welcher deterministisch oder nichtdeterministisch sein kann. Im Gegensatz zum Mealy Automaten hängt seine Ausgabe ausschließlich von seinem… …   Deutsch Wikipedia

  • Mealy-Automat — Ein Mealy Automat ist ein endlicher Automat, dessen Ausgabe (im Gegensatz zu einem Moore Automaten) von seinem Zustand und seiner Eingabe abhängt. Anschaulich bedeutet das, dass jeder Kante im Zustandsdiagramm ein Ausgabewert zugeordnet wird. Der …   Deutsch Wikipedia

  • Abstrakter Automat — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Keller Automat — Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der Theoretischen Informatik. Es handelt sich also um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”