Geschrieben von Shout22 am 10.07.2009 um 20:08:
epsilon-NFA zu DFA (lazy evaluation & table filling algorithmus)
Hallo,
ich habe folgenden epsilon-NFA:
http://img30.imageshack.us/img30/6597/epsilonnfa.jpg
Nun soll ich mit Hilfe der "lazy evaluation" einen DFA, nennen wir ihn A, konstuieren, der die selbe Sprache akzeptiert.
Anschliessend soll ich aus dem soeben konstruierten DFA (A) einen äquivalenten DFA, nennen wir ihn A', bestimmen, mit einer minimalen Anzahl von Zuständen. Und dies mit Hilfe des Table Filling Algorithmus.
Als Ergebnis ders ersten Punktes (lazy evaluation), habe ich einen DFA mit lediglich 4 Zuständen, die ich {q0AC} , {BCF} , {ADF} und {BDF} genannt habe.
Problem ist nun, beim Table Filling Algorithmus, ist es aus meiner Sicht nicht mehr möglich den Automaten zu minimieren. Stimmt das oder hab ich da irgendwo nen ganz groben Schnitzer drinne?
Ich stelle mir diese Frage, da dies eine Klausurvorberitungsaufgabe ist und ich mir nicht vorstellen kann, dass hier ein Beispiel ohne Minimierbarkeit gewählt wurde.
Schon einmal recht herzlichen Dank!
LG, Shout22