epsilon-NFA zu DFA (lazy evaluation & table filling algorithmus) |
| 10.07.2009, 20:08 | Auf diesen Beitrag antworten » |
| Shout22 | 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 |
|
|
|
| 23.02.2010, 21:13 | Auf diesen Beitrag antworten » |
| Gast | RE: epsilon-NFA zu DFA (lazy evaluation & table filling algorithmus) Du hast einen Zustand übersehen: {AC} - Dann "lohnt" sich auch der table-filling- Algorithmus. |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
