FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

[FGI 1] NFA zu DFA: Mehrere Startzustände

[FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-17 15:07
Hannes
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?

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-17 15:10
doodles
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

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-17 15:38
Fred
Du musst die Epsilon-Hülle von {z0, z1} nehmen.

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-17 15:42
Hannes
okay, danke euch :)

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-17 19:21
doodles
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]

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-17 21:20
Anonymer User
welche epsilon übergänge habt ihr denn?

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-17 22:07
doodles
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.

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-17 22:31
Anonymer User
alles klar ;)

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-18 00:08
Fred
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.

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-18 15:00
Anonymer User
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?

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-18 16:15
doodles
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.

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-18 16:31
Anonymer User
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.

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-18 16:44
doodles
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]

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-18 17:07
Anonymer User
Das würde bedeuten, der Automat C besteht aus zwei aneinander geklatschten Automaten(A und B), die in keinster Weise miteinander verbunden sind,oder?

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-18 17:09
doodles
jupp

RE: [FGI 1] NFA zu DFA: Mehrere Startzustände 2007-06-18 18:35
Anonymer User
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…