Endlicher Automat < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:25 Sa 07.06.2008 | | Autor: | Parkan |
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich soll aus einem Zustandsdiagramm (NFA) das äquvalente Zustandsdiagramm (DFA) bauen. |
Hallo
Hat ein DFA immer nur ein einzigen Startzustand? Ich soll aus einem NFA den äquvalenten DFA bauen. Der NFA hat 2 Startzustände was mich sehr irretiert. Muss der DFA auch 2 haben?
Gibt es Programme die aus einem NFA selbst automatsich ein DFA machen?
Danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:18 Sa 07.06.2008 | | Autor: | Infinit |
Hallo Parkan,
ich kenne solche Automaten eigentlich immer nur mit einem Startpunkt,denn es ist ja gerade die Eigenschaft solch eines Punktes, der Startpunkt zu sein. Auf der anderen Seite kann es natürlich mehrere Anfangsbedingungen für solch einen Automaten geben, warum eigentlich nicht.
Was die Umwandlung anbelangt, da habe ich eine recht schöne Beschreibung des dazugehörigen Algorithmus gefunden, ![[]](/images/popup.gif) hier ist er.
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Antwort) noch nicht fertig  | | Datum: | 19:53 Mi 11.06.2008 | | Autor: | Shurakai |
Ein EA (endlicher Automat) hat per definitionem immer nur einen Zustand.
Eine weitere Beschreibung zur Konstruktion eines DEAs findest du auch bei der Uni Köln:
http://www.scale.uni-koeln.de/files/Mitschrift.pdf
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 21:26 Mi 11.06.2008 | | Autor: | Martin243 |
Hallo,
man muss hier genau zwischen deterministischen ud nichtdeterministischen endlichen Automaten unterscheiden. Beim NFA gibt es nicht einen Startzustand sondern eine Menge von Startzuständen (s. U. Schöning: Theoretische Informatik - kurzgefasst)
Gruß
Martin
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 16:57 Di 17.06.2008 | | Autor: | Shurakai |
Beide Möglichkeiten sind völlig äquivalent; man kann mittels Epsilon-Übergängen ja auch mit einem Startknoten beliebig viele andere Knoten zu "Startknoten" machen, von daher sind beide Definitionen völlig i.O.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Do 12.06.2008 | | Autor: | Gilga |
Also ein DFA hat nur einen Zustand
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:24 Do 12.06.2008 | | Autor: | Martin243 |
Genau. Nur beim NFA ist es eben anders.
|
|
|
|
