 DFA in NFA umwandeln |
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
 |
|
Wie wandle ich einen NFA in einen DFA um? Erstmal ohne Epsilon-Übergänge.
Zustände sind die Potenzmenge, das ist klar. Startzustand bleibt gleich und auch die akzeptierten Zustände sind klar. Nur: Wie bekomme ich die Übergänge?
__________________
Meine Moviebase
|
|
24.02.2008 13:09 |
|
|
kiste
Mitglied
Dabei seit: 06.05.2007
Beiträge: 29
|
|
Es wird in die Vereinigung jener Zustände über gegangen in der die einzelnen Zustände übergingen.
z.B.
z0 geht mit a über in z0 und z3
z1 geht mit a über in z0, z2, z3
dann geht {z0,z1} mit a über in {z0,z2,z3}
|
|
|
24.02.2008 13:41 |
|
|
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
und welche Übergänge hat der DFA von z0 und z1?
__________________
Meine Moviebase
|
|
|
24.02.2008 14:44 |
|
|
kiste
Mitglied
Dabei seit: 06.05.2007
Beiträge: 29
|
|
Ich verstehe deine Frage nicht ganz. Wie wärs wenn du einmal ein komplettes Beispiel angibst das du nicht verstehst
|
|
|
24.02.2008 21:26 |
|
|
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
Also, wenn iich hier folgenden NFA habe
Q = {1, 2, 3}
q_0 = [1}
F= {3} und
Delta = (1, a) = 2
(2, b) = 3
(2, a) = 3
Wie sieht das dann also DFA aus?
Q' = Potenzmenge von Q, also insgesamt 7 Zustände
F' = alle Zustände, die einen akzeptierten "enthalten", q_0' = q_0
Und wie mache ich jetzt die Übergänge?
__________________
Meine Moviebase
|
|
|
24.02.2008 21:36 |
|
|
kiste
Mitglied
Dabei seit: 06.05.2007
Beiträge: 29
|
|
komisches Beispiel 
In deinem Beispiel ist der Automat doch schon ein DFA, also wird der konstruierte DFA gleich dem gegebenen Automaten sein
|
|
|
24.02.2008 22:15 |
|
|
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
Ups! Da werde ich wohl nicht mehr ganz bei der Sache gewesen sein! 
__________________
Meine Moviebase
|
|
|
24.02.2008 22:47 |
|
|
|
