Hi,
kann mir je man sagen wie man aus einer NFA einen äquivalenten lambda freien automaten konstruiert??
Aus den theorem 3.25 bin ich nicht ganz schlau geworden.
Was bedeutet : ( IdZ U —> )^ |Z|-1 ????????????
Danke.!!!!!!!!!!!!!!
M1:
IdZ = Identität auf Z,
das ist eine relation, nämlich diese: (z,z) für alle z e Z
Z = menge der zustände des automaten
M2:
—>lambda soll die relation sein, die alle lambda-kanten
im automaten wiedergibt,
also (p,q) für alle lambda-kanten von p nach q
M3:
M1 und M2 sind zwei Mengen, diese werden durch U vereinigt zu
einer gesamtmenge: M1 u M2
M4:
nun wird das ganze malgenommen, |Z|-1-mal M3 mit sich selber
(das entspricht dem transitiven abschluss von M3),
das produkt zweier relationsmengen bedeutet in diesem Zusammenhang
etwa folgendes:
M * N = {(x,y) für (x,z) e M & (z,y) e N}
kurz gesagt neben all der theorie:
man bildet den reflexiven transitiven abschluss der Menge M2,
der vorhandenen lambda-kanten,
reflexiv heißt, dass die Identität dabei ist, also M1,
transitiv bedeutet, dass aus (a,b) und (b,c) in der relation folgt,
dass auch (a,c) in der relation ist
beispiel:
für einen automaten mit zwei lambda-kanten von Z1 nach Z2 und
von Z2 nach Z3 sieht das nun so aus:
(Z1,Z2) und (Z2,Z3) sind in der relation die grund-lambdakanten,
durch den reflexiven abschluss kommen (Z1,Z1), (Z2,Z2), (Z3,Z3) hinzu
bedeutung: man kommt mit dem wort lambda von Z1 nach Z1,
von Z2 nach Z2 und von Z3 nach Z3
der transitive abschluss, also dieses ominöse mal-nehmen von
zwei mengen, liefert hier nur ein neues paar,
nämlich (Z1,Z3), da man ja über Z2 mit 2x lambda-lesen
von Z1 nach Z3 kommt
den reflexiven transitive abschluss der Menge M2,
also der lambda-kanten, ist in diesem beispiel nun:
{(Z1,Z2),(Z2,Z3),(Z1,Z1),(Z2,Z2),(Z3,Z3),(Z1,Z3)}
und nun kann man fröhlich die neue kantenmenge des
lambda-freien NFAs bestimmen,
sagen wir mal der automat sah vorher so aus:
l = lambda, Z1= startzustand, {Z3} = menge der endzustände
.---. l .--. l .---.
||Z1| ----> |Z2| ----> |Z3||
'---' '--' '---'
<---- <----
b a
dann geht man so vor:
man geht jede nicht-lambda-kante durch,
fangen wir mit Z2 --b--> Z1 an:
nun kommt eine neue b-kante
von jedem zustand,
der über lambda-kanten mit Z2 verbunden ist,
zu jedem zustand,
der über lambda-kanten mit Z1 verbunden ist,
also so:
b b
.-. .-.
v | v |
.---. l,b .--. l,b .---.
||Z1| ----> |Z2| ----> |Z3||
'---' '--' '---'
<---- <----
b a
------------------------>
b
zum beispiel neu dabei: Z1 ---b---> Z3,
da Z1 über lambda-kanten mit Z2 verbunden ist,
über b mit Z1
und dann über lambda-kanten mit Z3
nun noch mal das gleiche für a:
b a,b a
.-. .-. .-.
v | v | v |
.---. l,a,b .--. l,a,b .---.
||Z1| ------> |Z2| ------> |Z3||
'---' '--' '---'
<---- <----
b a
-------------------------->
a,b
dann entfernt man die lambda-kanten und
da man von Z1 über lamdas in einen endzustand kommt (Z3)
muss Z1 auch noch endzustand werden,
dann ist es aber fertig, wenn ich keinen fehler gemacht habe ;)
b a,b a
.-. .-. .-.
v | v | v |
.----. a,b .--. a,b .---.
||Z1|| ------> |Z2| ------> |Z3||
'----' '--' '---'
<---- <----
b a
-------------------------->
a,b
Ich habe im Netz einen Algorithmus gefunden mit dem man einen NFA lambda-frei machen kann. Ich hab den an der Aufgabe 4.2 ausprobiert und habe einen NFA bekommen für den meiner Ansicht nach gilt: L(meinerVariante)=L(Musterlösung). Allerdings habe ich weniger Kanten als in der Musterlösung…
Mein NFA lautet:
A=({1,2,3}, {a,b}, K, {1}, {2})
K={(1,a,2),(1,b,3),(2,b,1),(2,a,2),(2,a,3),(2,b,3)}
Der Algorithmus (epsilon bwz. e = lambda):
NFA -> e-frei-NFA
Als ersten Schritt werden die spontanen Übergänge in einem NFA entfernt. Diese e-Übergänge bewirken stets, dass von einem State mit einem e-Übergang zu einem anderen State ohne Verzögerung oder Eingangssignal gewechselt werden kann. Um diese Übergänge zu entfernen bedarf es zwei einfacher Schritte:
Jeder nicht-akzeptierte State, der mittels mindestens einem e-Übergang zu einem Akzeptierer gelangen kann, kann selbst als Akzeptierer eingefärbt werden. Dabei spielt es auch keine Rolle, ob ein Übergang beispielsweise mit "0,e" beschriftet ist, solche ÜbergŠnge sind ebenfalls e-Übergänge. Dass diese
Abänderung keine Veränderung der akzeptierten Sprache einbringt, liegt auf der Hand, denn wenn ein nicht-Akzeptierer spontan in einen Akzeptierer wechseln kann, so wird auch der String, der in diesem nicht-Akzeptierer stoppen würde in dem Akzeptierer stoppen.
Solange von einem ersten State m ein e-Übergang zu einem zweiten n führt, so können alle Übergänge, welche beim zweiten State beginnen, auch beim ersten hinzugefügt werden. Der betreffende e-Übergang kann danach gelöscht werden. Wiederum steckt eine einfache Überlegung dahinter: Wenn von
einem State spontan in einen zweiten gewechselt werden kann, so bedeutet dies, dass er dieselbe Funktionen annehmen kann, wie der zweite. In Folge müssen also alle States, die von dem zweiten State erreichbar sind auch vom ersten aus erreichbar sein. Sodann ist der e-Übergang Überflüssig und kann entfernt werden.
Vielleicht möchte M.J. sich ja auch dazu äußern ;)
Ich kann so auf den ersten Blick keinen Fehler in der Argumentation entdecken. Muesste man natuerlich noch formal beweisen, dass man mit dieser Konstruktion immer einen aequivalenten, lambda-freien Automaten erhaelt.
ich bin auch entzückt und gespannt,
warum nicht dieses verfahren verwendet wird
wen es interessiert, mein beispiel von unten sieht dann
glaub ich so aus, deutlich einfacher ;) :
b a
.-. .-.
v | v |
.----. b .---. a .---.
||Z1|| <---- |Z2|| <---- |Z3||
'----' '---' '---'
---->
a
Dann fehlt ja nur noch die Genehmigung unseres Lehrmeisters M.J.
Und wer hats erfunden?
Ein Schweizer ;)
