Hab mal ne Frage zur Aufgabe 4.2:

Das Theorem 3.25 aus dem Skript soll ja streng angewendet werden zur Konstruktion des lambda-freien, buchstabierenden NFA, aber ich kann mir nich vorstellen, dass man nur das Skript nochmal abschreiben soll. So wie ich das sehe, gibt es beispielsweise nur einen Zwischenzustand q' und q1 wird auch nich zum Endzustand. Dann passt doch aber das Theo ausm Skript nich mehr, oder!?

Was meint ihr dazu?

Also ich hab eh meine probleme um das was das Skript sagt überhaupt zu entschlüsseln…Rein intuitiv würd ich das in 2 schritten machen.

ersma den normalen DFA:
[img]http://www.lagourmanderie.de/NFA_A.jpg[/img]

dann den lambda freien DFA:
[img]http://www.lagourmanderie.de/NFA_A_lambda.jpg[/img]

und nun den buchstabierenden:
[img]http://www.lagourmanderie.de/NFA_A_buchstabierend.jpg[/img]

könnte mir nun jemand sagen ob dies das "streng" angewendete Verfahren iss? Und wenn nich wie den das verfahren "streng" anzuwenden iss??

Womit hast du denn die schoenen Bilder erzeugt?

photoshop

Aba du kannst mir ja ma sagen ob die schön und richtig sind ;)

bitte ich flehe um ANTWORT! ;-)

naja, hab ich soweit auch, bis auf die Kante b nach q3. Wie kommst du denn darauf? welches wort soll das denn sein?

meinst du im zweiten diagram? Das kommt so zu stande das du wenn du noch lambda drin hast ja von q2 nach q1 kommst ohne buchstabe(wegen lambda) und von q1 könntest du ja dann wiedda in q3 über b. Also musst du doch im lambda freien diagram das so machen das du von q2 in q3 über b hinkommst oda nich?? ich bin mir ja bei der ganzen sache ja selbst nich so sicher…

[edit]aba eigentlich müsste das schon dahingehend stimmen weil du dann ja sonst schon in einen schritt deinen fertigen buchstabierenden automaten feddig hättest. Ich weiss nich ob uns janzen das so einfachen machen will[edit]

jo, das lässt mich auch zweifeln. na ich habs so:

buchstabierend:

q1 mit ner a-Schleife um sich selbst und ner a-kante zu q2
von q2 ne b-kante zu q1 und ne a-schleife zu sich selbst sowie ner a-kante zu q3. also hab ich keine kante mit 2 buchstaben.

wenn die unproduktiven entfernt sind, müssten dann nur noch q1 und q2 übrig bleiben mit den genannten kanten.

also da binni mir fast sicher das des nich ganz richtig iss:
1. wo bleibt den da {q1,b,q3} aus dem ursprüngliche NFA?
2. lambda geht ja nur von q2 nach q1, also müsste ne a-schleife um q2 ausreichen. Die um q1 würd ich weglassen.

oh, na jetzt hab ich mir das erstma durchdacht, wie du das meintest mit der b-kante. Stimmt !
Ich bin mir allerdings mit der a-Schleife um q1 nich sicher:
(q1,w,q3) durch (q1,a,q2),(q2,lambda,q1),(q1,b,q3) d.h. w= a,b

wär ja sonst in dem neuen nfa mit der b-kante von q2 nach q3 möglich, aber muss die schleife dann nich doch da rein?

na hast wohl recht..

na unproduktiv heißt doch, dass alle zustände, die kein Endzustand sind bzw. zu einem führen entfernt werden mit den dazugehörigen kanten…

Wie schreibt man das alles eigentlich formal auf? Ich denk mal, die Graphen allein reichen wohl nich. Einfach die Theoreme abschreiben und statt z immer q schreiben? Wär ja wohl ein bisschen einfach oder?

ich hab das einfach so gemacht:
NFA B, B := ({q1,q2},{a,b},{(q1,a,q2),(q2,b,q1),(q2,a,q2)},{q1},{q2})

[img]http://www.lagourmanderie.de/NFA_B.jpg[/img]

feddig

hat ma jemand n plan nach welchen regeln man die kanten für das diagram des vDFA zeichnen soll. Ich kann bei dem beispiel im skript kein schema erkenn.

och kommt schon, ihr könnt mir doch nich erzählen das sich keine sau für des topic intressiert. Ich will morgen mindestens 3 neue posts dazu sehen ;)

Muss bei dem buchstabierenden nich auch noch ne a-Kante von q2 nach q3, damit das (q2,a,q3) akzeptiert wird?

Naja, jedenfalls hab ich dann beim vNFA 3 Zustände {q1}, {q1,q2} und {q2} ({q1},a,{q1,q2}),({q1,q2},b,{q1}),({q1},a,{q2}),({q1,q2},a,{q2}),({q1,q2},q,{q1,q2})
Da is bestimmt noch ein Fehler drin aber so ungefähr muss es aussehen…

och kommt schon, ihr könnt mir doch nich erzählen das sich keine sau für des topic intressiert.

Doch, F guck ich mir nicht vorm Wochenende an [img]http://www.fb18.de/gfx/24.gif[/img]

Muss bei dem buchstabierenden nich auch noch ne a-Kante von q2 nach q3, damit das (q2,a,q3) akzeptiert wird?

Naja, jedenfalls hab ich dann beim vNFA 3 Zustände {q1}, {q1,q2} und {q2} ({q1},a,{q1,q2}),({q1,q2},b,{q1}),({q1},a,{q2}),({q1,q2},a,{q2}),({q1,q2},q,{q1,q2})
Da is bestimmt noch ein Fehler drin aber so ungefähr muss es aussehen…

hab ich mir auch gedacht…also der buchstabierender Automat der da steht iss ja eigentlich nich mehr äquivalent, weil mann ja von q2 nach q3 schon das wort ab gebildet hat, und man hat ja beim original NFA A ja die wahl zwischen a und b auf dem weg von q2 nach q3. Aba ich hab nur die Definition im skript "streng" angewendet…

Bei den zuständen haste die leere Menge vergessen.Und wie bistu auf die Zustandsüberführungen gekomm, nach welchem prinzip haste die den gefunden?

Morpheus wie geht das mit dem Zeichnen?
Mit Adope Photoshop?
Wie kriegst du das hier rein??????

@Morpheus

also ich hab im moment nur an der uni internet,
da müsstest schon komplette fragen und komplette zugehörige skriptdefinitionen aufschreiben/ linken für komplette antworten,

das lambdafrei-machen sieht ganz gut aus,
das buchstabierend machen dagegen nicht,

QUOTE:
"also der buchstabierender Automat der da steht iss ja eigentlich nich mehr äquivalent, weil mann ja von q2 nach q3 schon das wort ab gebildet hat, und man hat ja beim original NFA A ja die wahl zwischen a und b auf dem weg von q2 nach q3. Aba ich hab nur die Definition im skript "streng" angewendet…
ENDQUOTE

na die definition möchte ich sehen

aus (q2,ab,q3) könntest ja gerne (q2,a,q4) (q4,b,q3) machen,


aber gegeben ist (q2,a,q3),(q2,b,q3), das ist doch schon wunderbar buchstabierend


das unproduktiv-rausschmeissen sieht dann auch wieder gut aus

versteh ich dass nun richtig, dass der lambda freie NFA zugleich auch der lambda-freie, bustabierende NFA ist???

versteh ich dass nun richtig, dass der lambda freie NFA zugleich auch der lambda-freie, bustabierende NFA ist???

Wenn ichs richtig sehe, in diesme Fall ja. Buchstabierend heißt, dass an jeder Kante nur BUCHSTABEN stehen, keine Wörter. Es darf natürlich trotzdem kanten wie "a,b" geben weil das ja im Endeffekt nur zwei einbuchstaben-kanten sind. Nur dinge wie "abc" dürfen nicht mehr an einer Kante stehen.

Jo, äquivalent is der dann nich mehr. Also wo genau steht das denn im Skript?

Die leere Menge gehört nicht zu dem Diagramm (hatte Jantzen in der Vorlesung jedenfalls auch nicht drin). Hab einfach geguckt, wie ich zu welchem Zustand kommen würde…

Morpheus wie geht das mit dem Zeichnen?

gut geht das

Mit Adope Photoshop?

jau

Wie kriegst du das hier rein??????

mussu n server habn, und das per FTP draufstellen. So hab ichs zumindest gemacht.

@slater:

Meine Probleme liegen nun daran das ich nicht verstehe wie sich die kanten in einem vDFA ergeben:
es gibt ein beispiel dafür in den slides vonner vorlesung (http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS03/F2/f2slides4NFADFA.pdf.gz), im Skript habn wir aba noch ein anderes. Ich rall einfach nich wie sich halt die kanten und deren buchstaben bilden von Zustandsmenge zu Zustandsmenge.

@Morpheus:

Also, bin mir eigentlich sicher, dass um q1 doch ne a-Schleife muss, da ja beim alten NFA gilt: (q1,a,q2),(q2,lambda,q1) d.h. w=a
Das würde es aber ohne a-Schleife nich beim neuen NFA geben.

Beim Potenzautomaten versteh ich das so: wenn ein Buchstabe von einem Zustand nirgendwo hinführt, dann geht ne Kante zur leeren Menge (die muss nämlich doch mit rein) also z.B. ({q1},b,leer) ansonsten gilt wenn eine Kante von einem Zustand, der in einer Menge von Zuständen enthalten ist, dann führt die entsprechende Kante zu der Menge, die den Zielzustand enthält. Hoffe, das is so richtig und einigermaßen verständlich formuliert.

Aso: Ich glaub nich, dass man nen Zwischenzustand beim buchstabierenden miteinbauen soll, da ja keine Kante mit einem Wort existiert. Denn die Kante von q2 nach q3 heißt ja a,b und nich ab. Und das is ja nich das gleiche!

Falls noch andere dazu ne Meinung haben, könnten die das ja mal posten!

Es scheint so, als hättet ihr alle doch erst iii) gemacht, und davon dann aus auf ii) zurückgeschlossen; aber laut Aufgabe sollen wir es genau in der richtigen Reihenfolge aufbauen. Ich vestehe aber die Def. 3.25 nicht: was genau soll den die Relation z (Sternchen über Pfeil über lambda) z' bedeuten ? Wort soll doch eben nicht lambda sein, und gleichzeitg soll eine lambda von z zu z' führen ?

Und warum gibt es in diesem Skript nicht mal ein einziges Beispiel ;(

@Farcon
Der Pfeil mit dem * und dem lambda bedeutet eine lambda kante.
Also z1->z2 heisst, dass man mit lambda von z1 nach z2 kommt.
Hättest du die Bedingung mit w!=lambda nicht, wären die lambda-Kanten immer noch vorhanden.
Und die beiden Ausdrücke danach, stellen sicher, dass die lambda-Kanten durch andere Kanten ersetzt werden.
Ansonsten wäre ja die akzeptierte Sprache nicht mehr gleich.

jo stimmt, was beispiele angeht iss das skript echt schäbig.
Und was dem iii) vor ii) angeht, das iss zumindest in meinem fall nicht so. Ich hab ii) einfach nach "logischem gefühl" gemacht, und dann den diagramm aus iii) gemacht.

@Nostradamus: nee sorry ich habs zwar versucht, aba deine erklärungen rall ich nich ganz…:/

Hi,

auch wenn es vielleicht schon erwähnt wurde. Zu Aufgabe 4.2 (ii), geht Ihr glaube ich nicht nach der Definition von K' (im Skript 3.25), oder? Demnach dürfte in der Graphik für den neuen buchstabierenden lambda-freien NFA, weder um q1 noch um q2 eine Schleife für a vorhanden sein, da ja auch im eigentlichen NFA A keine Möglichkeit besteht ein leeres Wort nur mit q1 oder q2 zu bilden (sie sind ja beide keine Start- und Endzustände zu gleich, noch sind hier Kanten vorhanden, die uns zeigen, das hier Lambda von q1 nach q1 oder von q2 nach q2 führt)!! Vielmehr bildet sich durch die Definition für K' meiner Meinung nach eine Möglichkeit von q2 nach q1 das "Wort" a zu bilden!

LG Frischling

PS: Falls ich das irgendwie falsch sehe, bitte ich um Hilfe. (DAS WARUM!!!)

Du meinst also sowas?
a q1 ------> q2 <------ a,b
Das wäre nicht äquivalent, da das Wort aa nicht mehr akzeptiert wird.

Dass man mit lambda von q1 nach q1 kommt, ist glaub ich implizit.

aa würde eh nie akzeptiert werden.
Im gegeben Graph würde man da von q1 nach q2 und dann nochmal nach q3 gehen.
Und die Definition von K' ist genau die, die man verwenden soll.
Zumindest steht in der Aufgabe man solle Theorem 3.25 benutzen und darin steht, woraus die Menge K' besteht.
Ich glaube das klappt auch.
Die Schleifen sind da auch vorhanden.
Untersuch mal die Kante (q1,a,q2).

aa würde eh nie akzeptiert werden.

Doch, vom ursprünglichen Automat schon. Man gehe von q1 über a nach q2, dann über lambda wieder zurück, und über a wieder nach q2.

Wo das hier gerade auftaucht…
a-a ist doch nicht das gleiche wie a-lambda-a, oder?
Zumindest kommen da beim gegeben NFA unterschiedliche Zustände bei raus.

a-a ist doch nicht das gleiche wie a-lambda-a, oder??

Doch, ist es. Wenn Du ein Wort hast, und NICHTS anhängst, bekommst Du wieder das alte Wort.

OK…
Aber wieso gibt es dann lambda-Kanten? Das macht doch keinen Sinn.
z.B.:
Für den NFA aus der Aufgabe:
(q1,a,q2),(q1,a,q3)
(q1,a,q2),(q2,lambda,q1),(q1,a,q2)

Irgendwie ist das dann wohl doch nicht das Gleiche.
Oder meintest du, dass a-lambda-a für einen lambda-freien, äuqivalenten NFA das gleiche wie aa ist?

Die WÖRTER aa und a-lambda-a sind gleich. Die Automaten natürlich nicht. Im Beispiel kommst Du OHNE ETWAS ZU LESEN von q2 nach q1.

K':={(z,w,z''')€ZxE*xZ|es existiert ein(z',w,z'')€K:w ungleich Lambda(leeres Wort) und von z über Lambda nach z' und z'' über Lamda nach z''' (in A, also ürsprünglichem NFA)}

So steht das im Skript!

Daraus folgere ich, wenn wir im neuem Lambda-freiem NFA z.B. (q1,a,q1)=(z,w,z''') haben, dann müßte (q1,a,q2)=(z',w,z'')oder (q2,a,q3)=(z',w,z'') sein, da es sonst im ursprünglichem NFA keinen anderen Weg gibt über dem man a bilden kann.

Wenn das obengenannte so ist, dann müßte folgendes, gelten, damit (q1,a,q1) möglich ist:

(q1,lambda,q1) oder (q1,lambda,q3) und (q2, lambda, q1) oder (q3, lambda, q1): Nur (q2,lambda, q1) ist ein Element der Menge K in unserem ursprünglichem NFA, aber da es ein und gibt und (q1, lambda, q1) keine Element von K unseres ursprünglichem NFA ist, kann es somit kein q1<–a–>q1 im neuem NFA geben!

Dasselbe für q2:

(q2, a, q2)=(z,w,z'''), damit das für K' gilt, muß folgendes gelten:

(q1, a, q2) oder (q2,a,q3)= (z',w,z''), da ja w ungleich Lambda sein muß und wir die Möglichkeiten suchen das "Wort"/"Buchstabe" a zubilden.

(q2, lambda, q1) oder (q2, lamda, q2) und (q2, lambda, q2) oder (q3, lambda, q2), auch hier ist wieder zu sehen, dass (q2,lambda, q1) zwar ein Element von K ist, aber es gibt nicht gleichzeitig ein (q2, lambda,q2), das Element von K ist.

Wie schon gesagt q1 un q2 sind nicht Start- und Endzustand in einem und es führt im ursprungs NFA auch keine Kante dahin nach dem Motto q1<—lambda—>q1.

Also ich denke, das das was ich hier aufgeschreibselt habe, richtig sein dürfte, falls nicht, dann habe ich die Definition von K' im Skript nicht richtig verstanden.

LG Frischling

Wenn du nix, also lambda eingibst, kannst auch immer im gleichen Zustand bleiben.
Also (z, lambda,z) für alle z element Z.

Wenn du nix, also lambda eingibst, kannst auch immer im gleichen Zustand bleiben.
Also (z, lambda,z) für alle z element Z.

So seh ich das auch, allerdings muss ich Frischling Recht geben, dass das, wenn man genau hinguckt, so nicht im Skript steht. Insbesondere, wenn man noch die Definition von diesem Pfeil-mit-Stern-drauf dazunimmt (3.11), in der i > 0 gefordert wird.

Allerdings: Wie sollte der lambda-freie NFA denn sonst aussehen?

So seh ich das auch, allerdings muss ich Frischling Recht geben, dass das, wenn man genau hinguckt, so nicht im Skript steht.

Ich bin mir nicht sicher ob das im Skript stehen muss.

Die WÖRTER aa und a-lambda-a sind gleich. Die Automaten natürlich nicht. Im Beispiel kommst Du OHNE ETWAS ZU LESEN von q2 nach q1.

Es sollte eigentlich selbstverständlich sein, dass wenn ich nix lese, im gleichen Zustand bleiben darf.

So seh ich das auch, allerdings muss ich Frischling Recht geben, dass das, wenn man genau hinguckt, so nicht im Skript steht.

Ich bin mir nicht sicher ob das im Skript stehen muss.

Es geht hier um F. Da gilt alles, was nicht im Skript steht, erstmal als noch zu beweisen.

Desweiteren geht es hier um die Frage, ob (z, \lambda, z) \in K \forall z \in Z [1]. Da K in der Aufgabenstellung gegeben ist lautet die Antwort eindeutig NEIN.

Die WÖRTER aa und a-lambda-a sind gleich. Die Automaten natürlich nicht. Im Beispiel kommst Du OHNE ETWAS ZU LESEN von q2 nach q1.

Es sollte eigentlich selbstverständlich sein, dass wenn ich nix lese, im gleichen Zustand bleiben darf.

Also für mich isses selbstverständlich, ich wollte es nur der Vollständigkeit halber nochmal erwähnen.

<edit>Quoting repariert</edit>

[1] Sorry Mo, bin mal faul

Nee irgendwie rall ich das nich. Erstma find ich die Def im Skript schon voll verwirrend, da nich genau gesagt wird, was nun z', z'' und z''' sein sollen/ dürfen…

Wenn z nun q1 is, wie kommst du dann drauf, dass dann auch z' q1 is und so?

Ich find auch nich, dass ein Zustand gleichzeitig start und end sein muss, damit eine Schleife drumrum gehen kann. Und mit (q1,a, q2), (q2, a, q1), (q2, b, q1) und den andern beiden Kanten, kann der ja gar nich äquivalent sein. Was is z.B. mit w= aa von q1 nach q2? Dann geht ja nur: aba
oder w=a von q1 nach q1, was ja im NFA A möglich is, wenn du von q1 über a nach q2 wanderst und über lambda zurückspazierst!

Wie sieht denn der Graph aus???

Aba ma was andres: Wenn man nun (ii) falsch hat und die restlichen Dinger zwangsläufig drauf aufbauen, wird das dann als Folgefehler gewertet oder kann ich den restlichen schmu dann auch vergessen?

Wenn das obengenannte so ist, dann müßte folgendes, gelten, damit (q1,a,q1) möglich ist:

(q1,lambda,q1) oder (q1,lambda,q3) und (q2, lambda, q1) oder (q3, lambda, q1): Nur (q2,lambda, q1) ist ein Element der Menge K in unserem ursprünglichem NFA, aber da es ein und gibt und (q1, lambda, q1) keine Element von K unseres ursprünglichem NFA ist, kann es somit kein q1<–a–>q1 im neuem NFA geben!

Nicht ganz. Die Definition sagt in diesem Fall nur, dass es (q1,a,q2) geben muss. Die wege von z zu z' und z'' zu z''' (also hier q1 zu q1 und q2 zu q1) müssen nicht direkt in K sein, sondern nur als Rechnung existieren.

Und die Rechnung von q1 mit lambda nach q1 existiert. Nimm Definition 3.11 zur Hand. Sei p die leere Kantenfolge. Dann gilt für alle 0 < i <= 0, dass (z_i-1, x_i, z_i) ein Element von K ist, denn es gibt gar kein passendes i das dem widersprechen könnte. Damit existiert eine Rechnung von jedem Zustand zu sich selbst. Und damit kann man dei Schleife (q1,a,q1) problemlos bauen.

Sei p die leere Kantenfolge.

Argh. Da war die Denkblockade. Danke nochmal!

Nee irgendwie rall ich das nich. Erstma find ich die Def im Skript schon voll verwirrend,

Naja, das ist der Sinn an F, dass man an solche Formalismen gewöhnt wird.

da nich genau gesagt wird, was nun z', z'' und z''' sein sollen/ dürfen…

Erstmal sind alles 3 Elemente von Z.
(z, w, z''') \in ZxE*xZ ==> z''' \in Z
(z', w, z'') \in K (was ja eine Teilmenge von ZxE*xZ ist) ==> z', z'' \in Z

Und dann werden halt noch ein paar weitere Bedingungen an die zs gestellt.

…die Rechnung von q1 mit lambda nach q1 existiert. Nimm Definition 3.11 zur Hand. Sei p die leere Kantenfolge. Dann gilt für alle 0 < i <= 0, dass (z_i-1, x_i, z_i) ein Element von K ist, denn es gibt gar kein passendes i das dem widersprechen könnte. Damit existiert eine Rechnung von jedem Zustand zu sich selbst. Und damit kann man dei Schleife (q1,a,q1) problemlos bauen.

Also irgendwie kann ich die Definition 3.11 in meinem Skript nicht finden, dort gibt es nur 3.1 und 3.2 und aus 3.2 erkenne ich, dass ein leeres Wort in einem DFA nur möglich ist, wenn ein Zustand Start- und Endzustand zugleich ist.

Beispiel 3.3 aus dem Skript "[…]…Auch das leere Wort Lambda ist ein solches Wort und wird von dem Automaten akzeptiert, ohne den Startzustand zu verlassen. … […]"

Wie das nun bei einem NFA ist weis ich nicht.

Wenn es aber wirklich so ist, das ich ein leeres Wort bilden kann ohne eine Kante von q1 zu q1 zum Beispiel, dann gilt aber das selbe für q2! Und um beide Zustände kann ich eine Schleife mit a bilden.

LG Frischling

Edit: Hab Definition 3.11 gefunden!

Ok, die Rechnung mit Def. 3.11 ist zwar irgendwie logisch, aber müßte dann nicht auch eine Kante gezeichnet werden, die angibt, dass z.B. zu q1 ein Lambda möglich ist, oder ist das dann als Vorraussetzung aus dieser Rechnung gegeben?

Das aber q2—a—>q1 im neuem NFA ist müßte nach der Rechnung mit K' aufjedenfall sein!!!


LG Frischling

Ok, die Rechnung mit Def. 3.11 ist zwar irgendwie logisch, aber müßte dann nicht auch eine Kante gezeichnet werden, die angebit, dass z.B. zu q1 ein Lambda möglich ist, oder ist das dann als Vorraussetzung aus dieser Rechnung gegeben?

3.25 verlangt, dass es im K eine Rechnung von a nach a für das Wort lambda gibt, damit K' eine Kante (q1, a, q1) besitzt. Eine solche gibt es nach 3.11 immer. Eine Kante (q1, lambda, q1) muss es in K nicht geben.

Das aber q2—a—>q1 im neuem NFA ist müßte nach der Rechnung mit K' aufjedenfall sein!!!

Hmm… lass mal sehen:
z = q2
z' = q1
z'' = q2
z''' = q1
Tatsache, passt! Die hätt ich übersehen!

photoshop

Aba du kannst mir ja ma sagen ob die schön und richtig sind ;)

wie machst du da denn mit ps, ich schnall dass mit dem zeichnen nicht so ganz.

Also ich hab eh meine probleme um das was das Skript sagt überhaupt zu entschlüsseln…Rein intuitiv würd ich das in 2 schritten machen.

ersma den normalen DFA:

ähh, muss das nicht nfa heißen, der dann lambdafrei und bischstabiernd etc zum dfa gemacht wird?