Nichtdeterministische endliche Automaten (NEA)

Wiki-Quelltext dieser Seite.

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

;Die von <math>M</math> akzeptierte Sprache <math>L(M)</math> 
Ein NEA akzeptiert ein Eingabewort, wenn er beginnend in <math>q_0</math> nach endlich vielen Zustandsübergängen gemäß <math>\delta</math> in einen Endzustand übergeht und das gesamte Eingabewort gelesen wurde.

Das Eingabewort wird im Prolog-Programm als Liste repräsentiert.
<code id="4a98f0c4adf64">
accept(Xs) :- initial(Q), accept(Xs,Q).
accept([X|Xs],Q) :- delta(Q,X,Q1), accept(Xs,Q1).
accept([],Q) :- final(Q).
</code>

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

;Beispiel 
<math>M = (\{q_{0},q_{1}\},\{\texttt{a},\texttt{b}\},\delta,q_{0},\{q_{0}\})</math> mit<br/>
[[Bild:Nea-bsp01.jpg|300px]]

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

''Aufgabe'': Verwenden Sie AtoCC, um die von <math>M</math> akzeptierte Sprache <math>L(M)</math> festzustellen.

Der Beispiel-NEA kann nun direkt mit Prolog beschrieben werden:
<code id="4a98f0c4ae733">
initial(q0).
final(q0).
delta(q0,a,q1).
delta(q0,a,q0).
delta(q1,b,q0).
</code>

Wir fragen, ob das Wort aaaababababab zu der von dem Beispielautomaten akzeptierten Sprache gehört:
<eval id="4a98f0c4aef15">accept([a,a,a,a,b,a,b,a,b,a,b,a,b]).</run>

Hingegen wird aabb nicht akzeptiert.
<eval id="4a98f15e3ae6e">accept([a,a,b,b]).</run>

===Übungsaufgaben===

#Entwickeln Sie einen NEA für <math>L(M)=\{w\mid w=ab^*c\}</math>.
#Entwickeln Sie einen NEA für die Sprache der korrekt gebauten Variablennamen.