 |
|||
| HSG |
|
Konstruktion eines DFA aus einem NFA
Idee
Bei einem NFA kann man sich bei Mehrdeutigkeiten einen Weg aussuchen, der zur Akzeptanz führt. Diesen Mehrdeutigkeiten wird man gerecht, wenn man "Mengenzustände" einführt. Ein Mengenzustand nimmt dabei alle ursprünglichen Zustände auf, in die man bei einem erfolgreichen Weg gelangen könnte. Fehlerzustände werden also weggelassen und ein Endzustand in einem Mengenzustand macht diesen schon zu einem Endzustand.
Beispiel
NFA
aus Hopcroft/Ullman, Einf. i. d. Automatentheorie,.., S.23
b1.jff
Eine Möglichkeit, diese "Mengenzustände" und ihre Übergänge zu konstruieren, ist ein systematisches Vorgehen ausgehend vom Startzustand q0, er wird zum Mengenzustand [q0]. In der folgenden Tabelle werden Mengenzustände abkürzend aufgeführt: Statt [q0,q1] wird nur 0,1 geschrieben. Ist der Zustand ein Endzustand, so wird 0,1 geschrieben.
Bei der Eingabe 0 kann man in q0 bleiben oder nach q1 wechseln, daher der Eintrag 0,1. In diesem Mengenzustand [q0,q1] befindet sich ein Endzustand, daher 0,1. Die neuen Mengenzustände 0,1 und 1 werden in der Tabelle bei den Zuständen eingetragen, denn von dort könnte ein erfolgreicher Weg weitergehen. Bei der Ermittlung des Folge-Mengenzustands zu 0,1 müssen nun alle Möglichkeiten durchgespielt werden. Im Zustand 0,1 zu sein, bedeutet für den usprünglichen NFA, dass man im Zustand 0 oder im Zustand 1 ist.
Angenommen, man ist im Zustand 0.
Bei der Eingabe 0 ist der Zustand 0,1 der Folgezustand (man kann bei sich selbst "abschreiben", der Fall wurde weiter oben bereits erledigt).
Bei der Eingabe 1 ist der Folgezustand 1.
Angenommen, man ist im Zustand 1.
Bei der Eingabe 0 kommt man in den Fehler-Zustand F, bei der Eingabe 1 bleibt man in 1.
Es ergibt sich also 0,1,(F) als Folge-Mengenzustand, der Fehlerzustand F wird dabei weggelassen, da man nur an erfolgreichen Wegen interessiert ist.
Der Rest der Tabelle ergibt sich analog.
Tabelle
|
DFA
|
Aufgaben
Wandle die beiden folgenden NFAs (aus Hopcroft/Ullman, Einf. i. d. Automatentheorie,.., S.51) in DFAs um. Gib zum Test jeweils drei akzeptierte und drei nicht akzeptierte Worte an.
a) b2.jff,
Lösung
|
b) b3.jff,
Lösung
|
Elemente einer Python-Realisierung
# NFA in int-Darstellung
"""
anfz = 0
endz = {1}
fehz = 2
f = (({0,1},{1} ),
({2} ,{0,1}),
({2} ,{2} ))
"""
anfz = 0
endz = {1,3}
fehz = 4
f = (({1,3},{1} ),
({2} ,{1,2}),
({3} ,{0} ),
({4} ,{0} ),
({4} ,{4} ))
#-----------------------
def Folgezustand(zustand,eingabe):
"""
gibt zu einem 'Mengenzustand' zustand und einer Eingabe eingabe
die Menge der Folgezustaende zurueck
"""
fz = set([])
for z in zustand:
fz = fz|f[z][eingabe]
return fz
en = len(f[0]) # Anzahl der Eingaben
mz = [{anfz}] # Liste der Mengenzustaende
t = {} # Dictionary für Transitionen
i = 0
while i < len(mz):
for eingabe in range(en):
fz = set([])
for z in mz[i]:
fz = fz|f[z][eingabe]
if len(fz) > 1:
fz = fz-{fehz}
if (not fehz in fz) and (not fz in mz):
mz = mz+[fz]
if fz != {fehz}:
t.update({(i,eingabe):mz.index(fz)})
else:
t.update({(i,eingabe):'F'})
i = i + 1
endzustaende = set([])
n = len(mz)
for i in range(n):
for z in mz[i]:
if z in endz:
endzustaende = endzustaende|{i}
print(mz)
print(t)
print(endzustaende)