Nichtdeterministische endliche Automaten (NEA)

Aus ProgrammingWiki

Definition

Ein NEA ist ein 5-Tupel $M=(Q,\Sigma,\delta,q_0,E)$ , wobei $Q$ eine endliche nichtleere Menge von Zuständen, $\Sigma$ das Eingabealphabet, eine totale Überführungsfunktion $\delta: Q\times\left(\Sigma\cup\{\varepsilon\}\right)\mapsto \wp(Q)$ , $q_0$ einen Anfangszustand und $E$ eine Menge von Endzuständen bezeichnen.

Die von $M$ akzeptierte Sprache $L(M)$

Ein NEA akzeptiert ein Eingabewort, wenn er beginnend in $q_0$ nach endlich vielen Zustandsübergängen gemäß $\delta$ in einen Endzustand übergeht und das gesamte Eingabewort gelesen wurde.

Das Eingabewort wird im Prolog-Programm als Liste repräsentiert.

accept(Xs) :- initial(Q), accept(Xs,Q). accept([X|Xs],Q) :- delta(Q,X,Q1), accept(Xs,Q1). accept([],Q) :- final(Q).

Diese wenigen Code-Zeilen beschreiben die Arbeitsweise eines NEA ganz allgemein. Wir werden dies unten für einen Beispiel-NEA anwenden.

Beispiel

$M = (\{q_{0},q_{1}\},\{\texttt{a},\texttt{b}\},\delta,q_{0},\{q_{0}\})$ mit

Dieser Automat akzeptiert alle Wörter über $\{a,b\}$ , die aus beliebig vielen $a$ s bestehen. Hierzu gehört auch das leere Wort $\varepsilon$ . Ein akzeptiertes Wort kann auch bs enthalten, wenn vor einem solchen $b$ mindestens ein $a$ steht.