Parser und Übersetzer

Simulation eines nichtdeterministischen endlichen Automaten

Wir haben einen regulären Ausdruck in einen nicht­deterministischen 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 Start­zustandes). Anschließend werden ausgehend von den markierten Zuständen für jedes Zeichen des Eingabe­wortes die ent­sprechenden Folge­zustände sowie wiederum deren Epsilon-Hülle markiert. Ist nach dem letzten Zeichen des Eingabe­wortes ein Endzustand markiert, wird das Eingabewort erkannt, ansonsten zurück­gewiesen.

Klasse NfaSimulator

Die folgende Klasse NfaSimulator implementiert die Simulation des nicht­deterministischen 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 Folge­zustände unter dem Eingabe­zeichen 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.

 

from Nfa import *

class NfaSimulator(object):

    def __init__(self, nfa):
        self.nfa=nfa    # der zu simulierende Automat

    # simuliert den Automaten mit Eingabewort s
    def simulation(self, s):
        self.nfa.mark(False)    # alle Markierungen entfernen
        self.epsilonclosure=[]  # Queue
        self.activestates=[]    # Queue
        self.nfa.startstate.mark()
        self.activestates.append(self.nfa.startstate)
        for a in s:
            self.findEpsilonClosure()
            self.move(a)
        return self.findEpsilonClosure()

    # Bildet die Epsilon-Huelle aller Zustaende, die sich in der
    # Queue activestates befinden, und fuegt die Zustaende der
    # Epsilon-Huelle in die Queue epsilonclosure ein    
    def findEpsilonClosure(self):
        accepted=False
        while self.activestates!=[]:
            s=self.activestates.pop(0)
            self.epsilonclosure.append(s)
            if s==self.nfa.endstate:
                accepted=True
            if s.symbol=="$":     # Epsilon
                for t in s.nextstate:
                    if not t.marked:
                        t.mark()
                        self.activestates.append(t)
        return accepted

    # Bestimmt alle Folgezustaende der Zustaende in der
    # Queue epsilonclosure unter dem Zeichen a und fuegt
    # diese Zustaende in die Queue activestates ein
    def move(self, a):
        while self.epsilonclosure!=[]:
            s=self.epsilonclosure.pop(0)
            s.mark(False)
            if s.symbol==a:
                s.nextstate[0].mark()
                self.activestates.append(s.nextstate[0])

 

Um den Automaten v beispiels­weise mit dem Eingabewort abba zu simulieren, wird der Simulator wie folgt aufgerufen:

v=NfaSimulator(v)
accepted=v.simulation("abba")
if accepted:
    print "accept"
else:
    print "reject"

Zusammenfassung

Um fest­zustellen, ob ein Wort w von einem bestimmten regulären Ausdruck z erzeugt wird, konstruieren wir aus dem regulären Ausdruck z einen nicht­deterministischen endlichen Automaten N(z) (siehe Übersetzung regulärer Ausdrücke) und simulieren anschließend den Automaten mit dem Eingabewort w. Zur Ver­anschaulichung und zum Ausprobieren dient folgendes Applet.

 

Weiter mit:   [Applet zum Ausprobieren]   oder   [up]

 


H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 24.08.2012   Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden