Ich kann noch immer nicht aus der im Skript gegebenen Definition 3.25 Theorem schlau werden, wenn ich mir dann die Musterlösung zu Blatt 4 Aufgabe 4.1 (ii) angucke bin ich vollends verwirrt - kann mir jemand die Transformation anhand der Musterlösung erklären, plz… [img]http://www.fb18.de/gfx/26.gif[/img]

Für das generelle Verfahren, einen NFA Lambda-frei zu machen, schau Dir doch mal die Folien aus der Vorlesung an, da ist ein sehr gutes Beispiel zum Verstehen, wie ich finde.

Lade Dir am besten mal unter dieser Adresse (PDF-Doc.) die Folien aus der Vorlesung zum Thema NFA/DFA herunter und springe dann auf die Folie 39 (oder 49, wenn Du die Vorerläuterungen nicht brauchst). Auf den nächsten Folien wird das Verfahren recht anschaulich dargestellt, wie ich finde.

Bei weiteren Fragen kannst Du Dich ja noch einmal melden…

Ok - hatte mich schon vorher mit Skript+Folien beschäftigt,
musst du mir glauben, ich frag nicht bei jeder Kleinigkeit nach und bin auch nicht faul ( auf jeden Fall nicht übermäßig [img]http://www.fb18.de/gfx/25.gif[/img] )!

So, im Skript steht (~ Theorem 3.25 ):

Es gibt einen

[img]http://mokrates.de/cgi-bin/texstring?$NFA%20%5C,%20A:=%20(Z,%5CSigma,K,Z_%7Bstart%7D,Z_%7Bend%7D)$%20%5C%5C[/img]

der natürl. [img]http://mokrates.de/cgi-bin/texstring?$%5Clambda%20-%20Kanten$[/img] enthalten kann!

Ein neuer NFA B soll erklärt sein als:

[img]http://mokrates.de/cgi-bin/texstring?$NFA%20%5C,%20B:=(Z,%5CSigma,K',Z_%7Bstart%7D,Z'_%7Bend%7D)%20%5C,%20ohne%20%5C,%20%5Clambda%20-Kanten$%20%5C%5C%0D%0A%0D%0A$K'%20:=%20%5C%7B(z,w,z''')%5Cin%20Z%5Ctimes%5CSigma%5E%7B*%7D%5Ctimes%5CSigma%20%5C,%20%7C%20%5C,%20%5Cexists%20(z',w,z'')%20%5Cin%20K:$%20%5C%5C%0D%0A%0D%0A$w%20%5Cnot=%20%5Clambda%20%5Cwedge%20z%20%5Crightarrow%5E%7B*%7D_%7B%20%5Clambda%20%7D%20%5C,%20z'''%20%5C,%20(in%20%5C,%20A)%20%5C%7D%20$%20%5C%5C%0D%0A%0D%0A$Z'_%7Bend%7D:=Z_%7Bend%7D%20%5Cbigcup%20%5C%7Bz%20%5Cin%20Z_%7Bstart%7D%20%5C,%20%7C%20%5C,%20%5Cexists%20z'%20%5Cin%20Z_%7Bend%7D:%20z%0D%0A%20%5Crightarrow%5E%7B*%7D_%7B%20%5Clambda%20%7D%20z'%20%5C%7D$[/img]

Am Beispiel der Folien heißt das nach meinem Verständnis ->

(<- Fortsetzung hier weil "nur" 4 images erlaubt sind)

[img]http://img57.imageshack.us/img57/9348/kanteabcomp8sd.th.jpg[/img]

Wir haben hier zwei [img]http://mokrates.de/cgi-bin/texstring?$%5Clambda%20-Kanten$[/img].

Nach Definition des Skriptes setze ich
[img]http://mokrates.de/cgi-bin/texstring?$Z_0%20=%20Z'%20=%20Z''%20%5C,%20und%20%5C,%20Z_1%20=%20Z'''$[/img]
Es führt also eine
[img]http://mokrates.de/cgi-bin/texstring?$%5Clambda%20-%20Kante$%20von%20$Z$%20nach%20$Z'$%20und%20eine%20von%20$Z''$%20nach%20$Z'''$%20%5C%5C%0D%0ADa%20$Z'$%20und%20$Z''$%20durch%20ein%20wort%20(hier%20ab)%5C%5C%20verbunden%20sind,%20kann%20ich%20eine%20Kante%20von%5C%5C%0D%0A$Z=Z_0$%20nach%20$Z'''=Z_1$%0D%0Amit%20dem%20selbigen%20wort%5C%5C%0D%0Aziehen.[/img]

So weit die Erklärung bis zur ersten lambda-Kanten-Auslöschung -
die anderen werden analog elemieniert/ersetzt…

In einfachen Worten heißt das für mich:
Immer gucken wohin man mit einer lambda-Eingabe von Zustand1 kommt und dann von wo aus man vom erreichten Zustand kommen kann (also Zustand1 lambda-> Zustand2 beliebige Eingaben->? ).
Ich glaub das Schlagwort heißt hier lambda-Hülle!
Diese über den lambda-Umweg erreichbaren Zustände müssen von Zustand1 also erreichbar gemacht werden (beliebige Eingabe{w} von Zustand2 -> ZustandX wird zu Zustand1 w-> ZustandX) !

so tut mir leid, dass ich am Ende etwas Stil verloren habe, aber die Zeit drängt!!

Alles klar, ich versuche mal, das Zustandekommen der neuen Kantenmenge nah am Beispiel darzulegen. Uns wurde in der Übungsgruppe gesagt, daß wenn wir ein todsicheres Verfahren haben wollen, um den neuen lambda-freien NFA zu bekommen, wir folgendermaßen vorgehen sollen (ich erkläre es auch anhand der von Dir genannten Aufgabe 4.1.ii):

Zuerst bestimmst Du den sog. Lambda-Pfad, was hier folgende Kanten wären: (r,p) (weil von r nach p eine Lambda-Kante läuft) sowie (r,r), (s,s), (p,p), (q,q).

Danach machst Du Dir eine dreispaltige Tabelle, wobei Du die mittlere Spalte zuerst ausfüllst. Hier trägst Du untereinander alle Deine Kanten ein, die KEIN Lambda entahlten, also (p,a,q), (p,ba,q) usw…

Nun vervollständigst Du die linke und rechte Spalte der Tabelle. Du schaust Dir an, welche Kante Du jeweils in der mittleren Spalte hast. Angenommen, es ist die Kante (p,a,q). Dann schreibst Du in die linke Spalte alle Kanten des Lambda-Pfads (!), die in p enden und in die rechte Spalte schreibst Du alle Kanten des Lambda-Pfades, die in q anfangen. Dies machst Du nun Zeile für Zeile…

Für die Kante (p,a,q) sähen die drei Spalten also so aus:
(p,p) (r,p) — (p,a,q) — (q,q)

Nun generierst Du Dir die neuen Kanten für jede Zeile Deiner Tabelle, indem Du nach folgendem Schema vorgehst:
(A,p) — (p,a,q) — (q,B) —> daraus folgt neue Kante (A,a,B).

In unserer Beispielzeile würdest Du also (p,a,q) sowie (r,a,q) also zwei neue Kanten generieren.

Die neue Menge der Endzustände ist hier {p,r}, denn p war vorher schon Endzustand und r kommt hinzu, weil man von dem ehemaligen Startzustand r mit Hilfe einer Lambda-Kante in einen Endzustand (also p) kam.
Die Menge der (Start-)Zustände und die Menge der Eingabesymbole bleiben ansonsten gleich.

Ich hoffe, daß war soweit verständlich. Natürlich kann man den Lambda-freien NFA auch schneller und anders generieren, aber die Methode über diese Tabelle ist vergleichsweise wenig fehleranfällig, denke ich.

thanks
deine Methode ist super
jetzt verstehe ich endlich wie in 4.1 (ii) die Kanten s,b,p p,a,q etc. zustande kommen!

Aber sag mal, hab ich den die Definition aus dem Skript richtig verstanden/wiedergegeben - denn aus der kann ich mir nicht die Methode ganz erklären, wie du gesehen hast
+
die schnellere Methode würde mich auch interessieren, hast du die auch drauf?

Ich bleibe nochmal nahe dran am Beispiel, um die Methode, die dahintersteckt, zu erläutern.

Nehmen wir uns aus dem Automaten A(4) aus der Aufgabe 4.1. mal den Zustand (s).
Du siehst, daß Du mit einem "b" nach (r) kommst, von wo aus Du mit einem lambda, also ohne Eingabe, bekanntlich zu (p) kommst. Um im lambda-freien Automaten dies zu "simulieren", mußt Du also eine Kante von (s) mit diesem b als Eingabesymbol direkt zu (p) machen.

Ganz generell: Wenn Du einen Zustand hast, aus dem eine Lambda-Kante hinausgeht, dann schaust Du Dir an, aus welchen anderen Zuständen in diesen Zustand alles Kanten hineingehen. Danach verbindest Du diese anderen Zustände mit dem per lambda erreichbaren Zustand und beschriftest die Kanten entsprechend.

Nichts anderes sagt das Theorem 3.25 ja auch aus (welches Du oben im übrigen nicht ganz korrekt wiedergegeben hast!):
- Du hast vier Zustände z,z',z'' und z'''.
- Es wird verlangt, daß die Verbindung zwischen z' und z'' nicht aus lambda besteht.
- Zwischen z und z' sowie z'' und z''' soll ein Lambda-Pfad bestehen.

Bei unserem oberen Beispiel mit dem beschrittenen Weg s->"b"->r und dann r->"lambda"->p heißt dies also, daß z=z'=s (lambda-Pfad), z'=s mit dem Wort w="b" nach z''=r und dann am Schluß z''=r mit "lambda" nach z'''=p. Alle Bedingungen sind erfüllt, so daß das Theorem nun sagt, daß man die Kante (z,w,z'''), also hier (s,b,p) aufnehmen darf.

die schnellere Methode würde mich auch interessieren

Eigentlich meinte ich damit nur, daß wenn man das ganze verinnerlicht hat und ohne Aufschreiben einer dreispaltigen Tabelle auch im Kopf erledigen kann, daß es dann noch schneller geht. [img]http://www.fb18.de/gfx/6.gif[/img]

nochmal danke.. [img]http://www.fb18.de/gfx/23.gif[/img]

Nichts anderes sagt das Theorem 3.25 ja auch aus (welches Du oben im übrigen nicht ganz korrekt wiedergegeben hast!):
- Du hast vier Zustände z,z',z'' und z'''.
- Es wird verlangt, daß die Verbindung zwischen z' und z'' nicht aus lambda besteht.
- Zwischen z und z' sowie z'' und z''' soll ein Lambda-Pfad bestehen.

Mmh, eigendlich habe ich gedacht ich hätte es auch so interpretiert - wo habe ich es den falsch wiedergegeben/skizziert ?

Dann schreibst Du in die linke Spalte alle Kanten des Lambda-Pfads (!), die in p enden und in die rechte Spalte schreibst Du alle Kanten des Lambda-Pfades, die in q anfangen. Dies machst Du nun Zeile für Zeile…

Für die Kante (p,a,q) sähen die drei Spalten also so aus:
(p,p) (r,p) — (p,a,q) — (q,q)

Nun generierst Du Dir die neuen Kanten für jede Zeile Deiner Tabelle, indem Du nach folgendem Schema vorgehst:
(A,p) — (p,a,q) — (q,B) —> daraus folgt neue Kante (A,a,B).

In unserer Beispielzeile würdest Du also (p,a,q) sowie (r,a,q) also zwei neue Kanten generieren.

ich versteh das nich :(

kannste das noch mal genauer erklären?