e-NEA direkt in einen DEA umwandeln?
-
Hi Leute!
Die letzten Wochen hab ich ja immer wieder Fragen zur Umwandlung eines e-NEA über NEA zu einem DEA gestellt. Nun hab ich mitbekommen (was aber in der Vorlesung nicht behandlet wurde), dass man vom e-NEA auch direkt in einen DEA wandeln kann. Also quasi ohne Umweg über den NEA. Könnt ihr mir sagen wie das geht?
-
Wie hast Du es bisher gemacht?
Mit der Potenzmengenkonstruktion kann man auch NFAs mit epsilon-Übergängen in einen DFA umwandeln.
http://de.wikipedia.org/wiki/PotenzmengenkonstruktionIch hab das selbt kürzlich mal implementiert. Thread vielleicht wenig hilfreich aber hier: http://www.c-plusplus.net/forum/287055
-
Mit der Potenzmengenkonstruktion kann man auch NFAs mit epsilon-Übergängen in einen DFA umwandeln.
Wenn mir ein DEA gegeben ist, kann ich den ohne weitere Probleme anhand der PMK in einen DEA umwandeln.
Die Potenzmengenkonstruktion ist mir soweit also klar. Mir gehts jetzt eher darum: Ich weiß nicht recht wie ich die PMK auf einen e-NEA anwenden muss; insbesondere wegen e-Transtionen.Da würde ich mich über Hilfe freuen!
-
Das funktioniert schon mit dem Algorithmus auf Wikipedia.
Such eben mal nach einem Beispiel. Falls Du absolut nichts findest, mal ich am Wochenende vielleicht mal eins auf.
-
So, ich hab das Verfahren jetzt ein paar mal geübt und bin auch schon auf die richtigen DEAs damit gekommen. Nun bin ich aber auf ein Problem gestoßen was ich nicht verstehe. Bisher hatten meine e-NEAs vom Startzustand aus immer mind. eine feste 0 oder 1 Transition. Jetzt hab ich aber einen e-NEA, der vom Startzustand aus nur eine einzige e-Transition hat. Wie gehe ich da dann vor? Hier ist das Bild dazu: http://imageshack.us/photo/my-images/64/26759311.jpg/
