fb18.de
/ Bachelorstudieng
/ PM Formale Informatik
[FGI 1] NFA zu DFA: Mehrere Startzustände
Hallo,
in
Aufgabenblatt 10 gibt es die Aufgabe, einen durch die Vereinigung zweier DFA entstandenen NFA in einen DFA zu überführen. Durch die Vereinigung hat der NFA allerdings zwei Startzustände. Wie gehe ich bei der Überführung damit um?
wenn der nfa als startzustände z0 und z1 hätte wäre das bei dem äquivalenten dfa halt der zustand {z0, z1}. Eben einfach der Zustand, der alle Startzustände enthält und sonst nichts
Du musst die Epsilon-Hülle von {z0, z1} nehmen.
Was ist die Epsilon Hülle? hab ich was falsches gesagt oder kommt das dann aufs selbe bei raus?
[edit]
ahh ok… die Epsilon Hülle ist die Menge der Zustände, die von einem bestimmten Zustand oder einer Menge von Zuständen erreichbar sind, ohne ein Eingabezeichen zu verbrauchen. Das würde dann also fast dem entsprechen, was ich gesagt habe, nur dass dort noch die Epsilon Übergänge mit eingebracht werden.
[/edit]
welche epsilon übergänge habt ihr denn?
Wenn überhaupt gibt es nur die Epsilon-Übergänge zu den Startzuständen von Automat A und Automat B. Das heißt, dass der Startzustand von dem DFA C' in jedem Fall einfach nur aus der Menge dieser beiden Startzustände besteht.
Ich kannte jetzt die konkrete Aufgabe nicht, hatte mir aber erlaubt, das Allgemeingültige auf die Aufgabe anzuwenden, von wegen z0 und z1 :) Ob es da irgendwelche Epsilon-Übergänge gibt, wusste ich nicht.
Ich bin imstande einen NFA in einen DFA zu überführen, aber diesen zusammengesetzten NFA, dazu noch mit epsilon-Übergängen kann ich nicht.Im Skript wird es nicht behandelt.Woher soll ich das Know-How dazu beziehen?
Also in der Übungsaufgabe gibt es eigentlich gar keine Epsilon-Übergänge, weil nach der Aufgabe der Automat C nur die Übergänge von A vereinigt mit den Übergängen von B hat. Wenn man also in A und B keine Epsilon Übergänge hat, hat man in C auch keine. Und der zusammengesetzte NFA ist eigentlich nichts anderes als jeder andere NFA. Der einzige Unterschied zum Skript ist wohl, dass er mehrere Startzustände hat (glaub ich zumindest… ich habe mir das Skriptbeispiel/die Skriptbeispiele nicht so genau angesehen). Und wie man damit umgeht steht oben.
Der Automat C muss doch 2 epsilon-Übergänge haben und zwar zu den beiden Automaten A und B.Der Startzustand ist weder Sa noch Sb, sondern ein neuer q - Skript Folie 47.Von diesem aus kann ich eben über epsilon-Übergänge die alten Startzustände von Automat A und B erreichen.
der Automat C muss nicht 2 epsilon-Übergänge haben, weil er einfach 2 Startzustände haben kann (siehe
http://de.wikipedia.org/wiki/Nichtdeterministischer_endlicher_Automat). Und nach der Aufgabe ist das auch der Fall, weil der Automat klar definiert ist. und in dem Quintupel steht, dass die Menge der Startzustände aus den Startzuständen von A und B besteht. Und die Menge der Zustände besteht aus der Menge der Zustände von A und der Zustände von B. Das heißt es kann keinen neuen Zustand q geben, weil das dann in dem Quintupel stünde.
Man kann zwei Automaten zusammenbasteln indem man einen neuen Startzustand einführt und 2 Epsilon-Übergänge benutzt. Das ist in dieser Aufgabe aber nicht der Fall.
[edit]
Auf Seite 49 im Skript steht "Es gibt NEA-Definitionen, die - wie beim DEA - von einem Startzustand ausgehen"
Dafür benutzt man dann den Kram mit den Epsilon-Übergängen.
[/edit]
Das würde bedeuten, der Automat C besteht aus zwei aneinander geklatschten Automaten(A und B), die in keinster Weise miteinander verbunden sind,oder?
Bei mir ist folgendes rausgekommen: Zwei neue Zustände, der erste mit einer Schlaufe über "b", dann eine Kante zu dem zweiten Zustand über "a".Nun bin ich am Überlegen, ob der 2. Zustand auch eine Schlaufe über "a" verpasst bekommen soll…