Nichtdeterministische endliche Automaten (NEA)
Aus ProgrammingWiki
- Definition
Ein NEA ist ein 5-Tupel , wobei
eine endliche nichtleere Menge von Zuständen,
das Eingabealphabet, eine totale Überführungsfunktion
,
einen Anfangszustand und
eine Menge von Endzuständen bezeichnen.
- Die von
akzeptierte Sprache
Ein NEA akzeptiert ein Eingabewort, wenn er beginnend in nach endlich vielen Zustandsübergängen gemäß
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
Dieser Automat akzeptiert alle Wörter über , die aus beliebig vielen
s bestehen. Hierzu gehört auch das leere Wort
. Ein akzeptiertes Wort kann auch bs enthalten, wenn vor einem solchen
mindestens ein
steht.
Aufgabe: Verwenden Sie AtoCC, um die von akzeptierte Sprache
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
.
- Entwickeln Sie einen NEA für die Sprache der korrekt gebauten Variablennamen.