Diskussion:Deterministischer endlicher Automat
Das Beispiel passt nicht zum Thema bzw. der Definition von DEA, denn der angegebene Automat ist ein Mealy-Automat und kein DEA (wie ja auch angegeben wird). Dieser sollte besser als Beispiel für die noch fehlende Seite zu Mealy-Automat verwendet werden.
Außerdem hält ein DEA nicht an, wenn er einen Endzustand erreicht. Ein DEA liest immer die ganze Eingabe. Nachdem die gesamte Eingabe eingelesen wurde gibt es dann die Möglichkeit, dass der DEA sich in einem Endzustand befindet. Man sagt, der DEA akzeptiert die Eingabe.
Zustandsmenge und Alphabet müssen nicht disjunkt sein.
"Es gibt eine Übergangsfunktion" ist unpräzise, denn die Übergangsfunktion ist bei einem DEA gegeben.
Anstatt die Kleiner-Relation auf eine Kardinalität und unendlich anzuwenden würde ich besser schreiben dass die Kardinalität in den natürlichen Zahlen liegen muss. Dass NEAs sich in DEAs umwandeln lassen, muss hier nicht als Kopie stehen.
Es sollte erwähnt werden, dass sich ein DEA minimieren lässt.
Die hier beschriebene Form des DEA wird auch endlicher Akzeptor genannt, der Link nach diesem Stichwort auf der Seite zu endlicher Automat führt momentan ins Leere.
- Dass NEAs sich in DEAs umwandeln lassen, muss hier nicht als Kopie stehen.
- Erledigt. Im Artikel Nichtdeterministischer endlicher Automat habe ich zwei Beispiele vür die Umwandlung gebracht. Fehlt noch der mathematische Hintergrund. Hier habe ich den Satz entfernt. --Arbol01 14:27, 1. Dez 2004 (CET)
- Es sollte erwähnt werden, dass sich ein DEA minimieren lässt.
- Ich werde mich daran machen, weil ich es auch für wichtig halte. Es wird allerdings noch etwas dauern, da ich schon länger keine DEAs mehr minimiert habe. --Arbol01 14:27, 1. Dez 2004 (CET)
Es gibt wohl einen Algorithmus, welcher die Minimierung eine DFA ermöglicht, bei gelegenheit, werde ich diesen mal hier hinzufügen an Hand eine Beispiels. Wen es interessiert, man kann ihn im Schöning mit dem Titel Theoretische Informatik - kurzgefasst finden. 4. Auflage ISBN 3-8274-1099-1
Zum anderen fällt mir die Frage ein, ob es überflüssig ist Beweise hinein zu bringen, welche Belegen, dass z.b. jeder NFA = DFA ist oder jeder DFA sich minimieren lässt oder sogar dass Jeder DFA / NFA die Regulären Sprachen akzeptiert. --Razorhawk 11:39, 21. Jan 2006 (CET)
>> Es gibt mehrere Algorithmen - es wäre interessant zu schreiben welche die schnellsten sind (für Mensch / Maschine). Am Rechner schein Hopcroft mit Laufzeit O(n lg n) am schnellsten zu sein (Space O(m n)). (nicht signierter Beitrag von 77.2.141.93 (Diskussion) 11:07, 8. Nov. 2011 (CET))
Wieso werden hier nur Alphabete und die Konkatenation betrachtet? DEA's werden über beliebigen Monoiden definiert.
legende zum bildbeispiel
Unter dem Bildbeispiel sollte vielleicht stehen, dass der doppelkreis (S0) den/einen möglichen endzustand markiert. der startzustand ist ja (etwas intuitiver) durch den pfeil, der von linksoben in das diagramm einbricht, erkennbar.--PascalC 19:31, 28. Mai 2006 (CEST)
unverständlicher Satz
Könnte jemand der mehr Ahnung von der Materie hat als ich, folgenden Satz neu formulieren:
"Für jeden Buchstaben aus dem Alphabet wird nun jede Zustandsmenge dahingehend aufgeteilt, dass die Überführungsfunktion die Zustände jeder neuen Menge den Buchstaben in eine jeweils eindeutige Menge abbildet."
Klingt glaub ich nicht nur für mich unverständlich. --4pf3154f7 13:33, 6.Apr. 2008 (CET)
- Da geb ich dir recht. Ich habs mehrfaqch lesen müssen, bevor ich die Idee der Äquivalenzklassenbildung darin wiedererkannt hab. Ich würde das jetzt hier ändern, aber ich frage mich, ob es nich klüger wäre den Markierungsalgorithmus in einen neuen Artikel auszulagern. Schließlich ist der Algo auch für Bisimulation von Kripkestrukturen ganz interessant. --Redmaniac 18:27, 6. Jan. 2009 (CET)
DEAs? NEAs!
Das Thema des Artikels sind doch DEAs. Ich sehe aber im gesamten Artikel nur Beipiele für NEAs, kein Einziges für einen DEA. Die Beispiele sind somit allesamt falsch. Wäre schön, wenn das mal jemand korrigieren könnte. (nicht signierter Beitrag von Stivy M. (Diskussion | Beiträge) 17:36, 15. Dez. 2014 (CET))
