Indet. Automat zu det. Automat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:34 Di 13.01.2009 | | Autor: | skydyke |
Hallo,
ich habe eine Frage zu der Umwandlung von indeterministischen zu deterministischen endlichen Automaten.
In der Vorlesung haben wir dafür 2 Schritte. Im ersten Schritt sollen die epsilon-Übergange beseitigt werden. Dazu muss man eine Menge aufstellen, soweit versteh ich das auch noch, das einzige Problem was ich habe ist, dass ich den daraus resultierenden Automaten nicht aufschreiben kann, da ich nicht verstehe wie die neuen Produktionsregeln zu stande kommen.
Ich weiß wie die Finalzustände zustande kommen und wie ich die Teilmengen konstruire.
Das einzige was mir fehlt sind die Produktionsregeln. Kann mir das vielleicht einer erklären?
Gruß
Sabrina
|
|
| |
|
Hi Sabrina,
also, du betrachtest zuerst im NEA den Startzustand [mm] z_0 [/mm] und die von diesem Zustand ausgehenden Kanten und die Beschriftungen ebenjener. Hier können - rein theoretisch - mehrere Kanten mit identischer Beschriftung stehen: Das ist ja gerade der "nichtdeterminismus".
Diese Zustände fasst du dann in einer Menge zusammen, somit hast du im DEA nicht mehrere sondern immer nur einen Zustand pro Kantenbeschriftung.
Das heißt du simulierst den NEA durch Potenzmengenkonstruktion; wenn man das weiter so macht, kriegt man insgesamt den DEA raus.
Einen richtigen Algo habe ich dir jetzt nicht gegeben, sondern nur eine Idee; den Algo findet man allerdings in jedem entsprechenden Fachbuch bzw. in im Internet veröffentlichten Skripten zu Vorlesungen der Informatik. (Bei Bedarf kann ich dir das gerne posten)
Lieben Gruß!
Christian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:21 Sa 17.01.2009 | | Autor: | skydyke |
Vielen Dank für deine antwort, hat mir auf jedenfall weitergeholfen. Den Algo dazu hab ich in meinem Skript gefunden.
Gruß
Sabrina
|
|
|
|
