Nichtdeterministischer endlicher Automat


Nichtdeterministischer endlicher Automat
Grafische Darstellung eines NEA

Ein nichtdeterministischer endlicher Automat (NEA, englisch: NFA=nondeterministic finite automaton) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.

Inhaltsverzeichnis

Definition

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

  • Q ist eine endliche Menge von Zuständen (\left| Q \right| < \infty).
  • Σ ist das Eingabealphabet, \left| \Sigma \right| < \infty.
  • \Delta \subseteq (Q \times \Sigma) \times Q ist die Übergangsrelation (oder Transitionsrelation).
  • S \in Q ist der Startzustand.
  • F \subseteq Q ist eine (endliche) Menge möglicher akzeptierender Zustände (Finalzustände). Wenn der Automat nach Lesen des Eingabewortes w \in \Sigma^* in einem Zustand aus F hält, so gehört w zur Sprache L\left(A\right).

Verhalten

Liest der NEA in einem Zustand q das Eingabesymbol a, dann wechselt er nichtdeterministisch in einen Nachfolgezustand, der durch die Übergangsrelation gegeben ist. Der Automat hat also die Wahl zwischen allen Zuständen p, für die (q,a,p)\in\Delta gilt.

Gibt es keinen solchen Zustand, bleibt der Automat vorzeitig stehen und verwirft die Eingabe.

Ein Eingabewort w gilt dann als akzeptiert, wenn es für w eine durch Δ gegebene Folge von Zustandswechseln gibt, bei der der Automat nicht vorzeitig stehen bleibt und der letzte Zustand ein akzeptierender Zustand ist.

Transition als Funktion

Alternativ lassen sich die Übergänge auch durch eine Transitionsfunktion definieren, die dann in eine Menge von Zuständen abbildet:

\mathcal{A} = \left( Q,\Sigma,\delta,S,F\right) mit \delta: (Q\times\Sigma) \to \mathcal{P}(Q)

Da die Funktion auch auf die leere Menge abbilden kann, sodass \delta(q,a)=\varnothing gelten kann, ist auch hier ein vorzeitiges Stehenbleiben möglich.

Epsilon-Übergänge

Ein NEA, der zur Sprache α die Sprache α * erkennt

Man kann NEAs auch so definieren, dass Zustandsübergänge möglich sind, bei denen kein Eingabezeichen gelesen wird. Vor oder nach dem Lesen eines Zeichens kann ein NEA also zufällig den Zustand wechseln. Die Zustände, die gewechselt werden können, werden durch Übergänge verbunden, die statt eines Symbols das leere Wort ε (manchmal auch λ) lesen. Diese Zustandswechsel werden ε-Übergänge oder ε-Schritte genannt. Bei grafischen Repräsentationen von NEAs werden die Übergänge als mit ε (oder λ) beschriftete Kanten dargestellt und deshalb auch ε-Kanten genannt.

Formal ermöglicht man diese Übergänge, indem man die Transitionsrelation erweitert:

\Delta \subseteq Q \times (\Sigma \cup \{\varepsilon\}) \times Q

Dabei ist sicherzustellen, dass ε nicht bereits in Σ vorhanden ist, sondern ausschließlich das leere Wort repräsentiert.

NEAs mit Epsilon-Übergängen können nicht mehr Wörter erkennen als ohne diese Erweiterung. Zu einem NEA mit Epsilon-Übergängen gibt es also immer einen äquivalenten NEA ohne Epsilon-Übergänge. Sie können aber die Konstruktion mancher Automaten vereinfachen. Beispielsweise kann man zu einem NEA \mathcal A mit wenig Aufwand einen Automaten \mathcal A' konstruieren, der die Kleene'sche Hülle der Sprache von \mathcal A akzeptiert, also \mathcal L(\mathcal A')=(\mathcal L(\mathcal A))^*.

Mehrere Startzustände

Ein NEA mit neuem Startzustand, der mit Epsilon-Übergängen die Startzustände von Teilautomaten verbindet

Es ist auch möglich, mehrere Startzustände zu erlauben.[1]

Der Automat ist dann definiert als \mathcal{A} = \left( Q,\Sigma,\Delta,S,F\right) mit S \subseteq Q.

Solche Automaten lassen sich mittels ε-Übergängen in NEAs mit genau einem Startzustand überführen, indem man einen neuen Zustand einführt, von dem aus man die ursprünglichen Startzustände durch ε-Übergänge erreicht.

Auf diese Weise kann man zu zwei Automaten \mathcal A, \mathcal B einen NEA \mathcal C erstellen, dessen Sprache die Vereinigung der Sprachen der beiden anderen Automaten ist, also \mathcal L(\mathcal C)=\mathcal L(\mathcal A)\cup \mathcal L(\mathcal B). Bei disjunkten Zustandsmengen von \mathcal A und \mathcal B muss man nur einen neuen Startzustand einführen, der über Epsilon-Übergänge mit den Startzuständen der beiden Automaten verbunden ist. Die Menge der akzeptierenden Zustände ist die Vereinigung der akzeptierenden Zustände der beiden Automaten.

Eigenschaften

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

Der wesentliche Unterschied des NEA zum deterministischen endlichen Automaten (DEA) liegt somit darin, dass auch mehrere Folgezustände möglich sind oder auch ganz fehlen können.

Um einen regulären Ausdruck in einen NEA zu überführen, sind gewisse Regeln zu befolgen.[2] Diesen Vorgang nennt man Induktive Konstruktion oder auch Thompsons Konstruktion.[3]

Siehe auch

Referenzen

  1. Katrin Erk, Lutz Priese: Theoretische Informatik: Eine umfassende Einführung. 3. Auflage. Springer, 2008, ISBN 3-540-76319-8, Seite 67
  2. Hans Werner Lang: http://www.inf.fh-flensburg.de/lang/theor/regulaerer-ausdruck-zu-automat-bottomup.htm
  3. Alfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison Wesley, 1986

Literatur

Weblinks


Wikimedia Foundation.

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

  • 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 …   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

  • 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

  • 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

  • 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

  • Push-Down-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

  • Myhill-Konstruktion — Die Potenzmengenkonstruktion (Myhill Konstruktion oder auch Teilmengenkonstruktion) ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt. Das… …   Deutsch Wikipedia

  • Teilmengenkonstruktion — Die Potenzmengenkonstruktion (Myhill Konstruktion oder auch Teilmengenkonstruktion) ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt. Das… …   Deutsch Wikipedia

  • Finite-State-Machine — Abb.1 Beispiel eines EA Ein endlicher Automat (EA, auch Zustandsmaschine, englisch finite state machine (FSM)) ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt endlich, wenn die Menge der… …   Deutsch Wikipedia

  • Finite State Machine — Abb.1 Beispiel eines EA Ein endlicher Automat (EA, auch Zustandsmaschine, englisch finite state machine (FSM)) ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt endlich, wenn die Menge der… …   Deutsch Wikipedia