Nichtdeterministische endliche Automaten (NEA)
- 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.
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 as 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.
Aufgabe: Verwenden Sie AtoCC, um die von M akzeptierte Sprache L(M) festzustellen.
Der Beispiel-NEA kann nun direkt mit Prolog beschrieben werden:
Wir fragen, ob das Wort aaaababababab zu der von dem Beispielautomaten akzeptierten Sprache gehört:
Hingegen wird aabb nicht akzeptiert.
Übungsaufgaben
- Entwickeln Sie einen NEA für L(M)=\{w\mid w=ab^*c\}.
- Entwickeln Sie einen NEA für die Sprache der korrekt gebauten Variablennamen.