NFA in DFA überführen Potenzmenge sehr groß?
Hallo,
ich wäre sehr dankbar, wenn mir jemand im Teil b) der Aufgabe weiterhelfen könnte:
Meine Lösung a)
0(1)*(101|01(0)*0)(0*1*)* als regulärer Ausdruck
b) Die Nichtdeterminus Stellen habe ich markiert im NFA
Jetzt soll man noch den NFA in einen DFA überführen. Normal bildet man doch jetzt die PotzenMenge, dies wären 2^7 = 128 Zustände (und arbeitet dort die Verbindungen ab...)
=> Dies kann man doch sicherlich einfacher lösen.
Bitte es so erläutern, dass es auch jemand versteht der nicht Profi in den Formalen Sprachen ist. Danke!
=> Wie sähe der DFA am Ende aus?
2 Antworten
Jetzt soll man noch den NFA in einen DFA überführen. Normal bildet man doch jetzt die PotzenMenge, dies wären 2^7 = 128 Zustände (und arbeitet dort die Verbindungen ab...)
Es reicht aus, wenn du nur die zustände betrachtest, die überhaupt erreichbar sind.
Fang also erst mit {{q_0}} an, und prüfe jedes Mal, ob du durch einen Übergang ein neues Element der Potenzmengen erreichen kannst. Füge das dann zu deiner Menge der erreichbaren zustände hinzu, und wiederhole das ganze, bis du keinen neuen Zustand von deinen bisher betrachteten zuständen erreichen kannst.
(Du würdest hier als nächstes also {q_1} hinzufügen, und dann {q_1, q_2} sowie {q_5} hinzufügen und so weiter)
Danke für deine Hilfe, aber die Erklärung von Desantrix ist noch ein Stück besser.
Du musst ja nur die Zustände extra aufschreiben, die mehrfach vorkommen können.
Du startest beim Startknoten. Für jeden Buchstaben des Alphabets zeichnest du einen Übergang im DFA und einen Knoten. Dieser Knoten steht repräsentativ für alle Knoten, die im NFA mittels des Buchstabens vom Startknoten aus erreichbar sind.
Das machst du für jeden Knoten des NFA für den der Knotend es DFA stehen kann.
Beispiel:
{(q0)} {}
{(q0), (q1)} {(q0) - 0 - >(q1)}
{(q0), (q1), (q1, q2), (q5)} {(q0)-0->(q1), (q1)-1->(q1, q2), (q1)-0->(q5)}
{(q0), (q1), (q1, q2), (q5), (q6), (q3, q5)} {(q0)-0->(q1), (q1)-1->(q1, q2), (q1)-0->(q5), (q5)-1->(q6), (q1, q2)-1->(q1, q2), (q1, q2)-0->(q3, q5)}
...
Für Epsilonübergänge fügst du beim Hinzufügen eines Knotens auch die Knoten hinzu, die von ihm aus über Epsilonübergänge erreichbar sind.
Ich stell nachher nochmal ein Bild von meiner Lösung ein.
MFG