e-NEA zu DEA
-
Hi Leute!
Ich hab hier eine Aufgabe zu einer Umwandlung von e-NEA zu einem DEA. Hier ist ein Link mit der kompletten Lösung dieser Aufgabe. Ich frage mich nun jetzt aber schon die ganze Zeit, ob es stimmt, dass es hier nur eine einzie kritische Kante gibt...
Ich würde mich sehr freun, wenn jemand von euch mit etwas mehr Ahnung, die Aufgabe kurz durchschaun könnte und mir sagt ob die Lösung stimmt oder nicht.
Hier ist der Link: http://imageshack.us/photo/my-images/585/88131352.jpg/
Danke!
-
Ja, ist die einzige kritische Kante. Wenn die Kanten von 3 nach 2 bzw. von 1 nach 3 andersrum wären, wären sie auch kritisch - aber so nicht.
-
Danke für die wahnsinnig schnelle Antwort
Genau auf den gleichen Entschluss, wie du, bin ich auch gekommen!
Die Umwandlung vom NEA in den DEA ist dann soweit auch richtig?
EDIT: Mir fällt grad auf, dass der Zustand {2,1} im DEA ja auch akzeptierend sein muss; da steckt ja auch der Zustand 2 vom e-NEA drin.
-
Genau das wollte ich auch gerade sagen, ansonsten seh ich auch keinen Fehler.
-
Danke, du hast mir sehr weiter geholfen!