Wir haben einen regulären Ausdruck in einen nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen übersetzt. Jetzt geht es darum, diesen Automaten zu simulieren, d.h. zu prüfen, ob er ein gegebenes Eingabewort w erkennt oder zurückweist.
Das Verfahren hierzu ist einfach: Zu Beginn wird der Startzustand des Automaten markiert sowie alle Zustände, die durch Epsilon-Übergänge vom Startzustand aus erreichbar sind (die Epsilon-Hülle des Startzustandes). Anschließend werden ausgehend von den markierten Zuständen für jedes Zeichen des Eingabewortes die entsprechenden Folgezustände sowie wiederum deren Epsilon-Hülle markiert. Ist nach dem letzten Zeichen des Eingabewortes ein Endzustand markiert, wird das Eingabewort erkannt, ansonsten zurückgewiesen.
Die folgende Klasse NfaSimulator implementiert die Simulation des nichtdeterministischen endlichen Automaten. Ausgehend von einer Menge von markierten Zuständen, die sich in einer Queue activestates befinden, realisiert die Funktion findEpsilonClosure den Schritt "Markiere alle Zustände, die durch Epsilon-Übergänge erreichbar sind"; die so markierten Zustände werden in einer zweiten Queue epsilonclosure gespeichert. Ausgehend von den Zuständen, die sich in der Queue epsilonclosure befinden, realisiert die Funktion move den Schritt "Markiere alle Folgezustände unter dem Eingabezeichen a"; die so markierten Zustände werden wiederum in der Queue activestates gespeichert. Die beiden Queues werden also im Wechsel von der einen Funktion gefüllt und von der anderen Funktion wieder abgearbeitet. Zu Beginn wird der Startzustand in die Queue activestates eingefügt.
Um den Automaten v beispielsweise mit dem Eingabewort abba zu simulieren, wird der Simulator wie folgt aufgerufen:
Um festzustellen, ob ein Wort w von einem bestimmten regulären Ausdruck z erzeugt wird, konstruieren wir aus dem regulären Ausdruck z einen nichtdeterministischen endlichen Automaten N(z) (siehe Übersetzung regulärer Ausdrücke) und simulieren anschließend den Automaten mit dem Eingabewort w. Zur Veranschaulichung und zum Ausprobieren dient folgendes Applet.
Weiter mit: [Applet zum Ausprobieren] oder [up]