NFA zu DFA umwandeln, Automaten (Mathematik / Informatik)?
Hi, ich lerne zurzeit den Algorithmus, um einen NFA zu einem DFA umzuwwandeln. Was ich hierbei nicht verstehe, z. B. beim markierten Puntk. Ich befinde mich bei {q0,q1}. Warum befinde ich mich bei {q0,q2}, wenn ich von dort aus eine 0 habe?
Wenn wir uns den NFA anschauen, so ist ja bei q1, wenn ich dort eine 0 oder eine 1 habe nur die Möglichkeit, dass ich zu q2 gehe und nicht bei q1 bleibe?
1 Antwort
Ich befinde mich bei {q0,q1}. Warum befinde ich mich bei {q0,q2}, wenn ich von dort aus eine 0 habe?
Wir starten bei den Zuständen q_0 und q_1 und bekommen bei beiden eine 0. q_0 führt mit einer 0 nur zu q_0, q_1 führt mit einer 0 nur zu q_2; deine neuen möglichen Zustände sind also q_0 und q_2
Wenn wir uns den NFA anschauen, so ist ja bei q1, wenn ich dort eine 0 oder eine 1 habe nur die Möglichkeit, dass ich zu q2 gehe und nicht bei q1 bleibe?
eben, genau deshalb steht da q_2 am Ende
Warum starten wir den bei q_0 und q_1
weil das deine Ausgangsmenge ist (linke Spalte). Diese bekommst du, wenn du in q_0 bist und einer 1 folgst - da kannst du entweder wieder in q_0 oder eben in q_1 rauskommen.
Warum starten wir den bei q_0 und q_1