Diskussion:Nichtdeterministischer endlicher Automat
aus Wikipedia, der freien Enzyklopädie
Die meisten Kommentare zu Deterministischer Endlicher Automat passen auch hier.
Anstatt einer Übergangsfunktion mit einer Potenzmenge als Zielmenge verwendet man lieber eine Übergangsrelation.
- Es sind beides sinnvolle Definitionen, auch wenn mir die Relation besser gefällt. --Marc van Woerkom 14:19, 13. Apr 2005 (CEST)
Bei der Übergangsfunktion/relation fehlt die möglichkeit der Epsilon-übergänge.
- Man muss nicht alle Varianten {NEA, DEA} x {mit, ohne Epsilon Transition} durchspielen. Wichtig ist, dass man die Äquivalenz aller dieser Modellvarianten kennt. Eine weitere (äquivalente) Modifikation ist {Einweg, Zweiweg}. --Marc van Woerkom 14:19, 13. Apr 2005 (CEST)
- Wo sind die NEA/e (epsilon übergang) zu finden? (Sollte IMO gesondert behandelt werden.)
Das mit dem Anhalten ist hier noch falscher als bei DEA. Von halten kann man bei einem NEA garnicht sprechen, denn ein NEA ist eben nicht deterministisch. Man kann nur definieren, wann ein NEA ein Wort w akzeptiert, und zwar wenn es eine Folge von Zustandsübergängen zu diesem Wort gibt, so dass sich der NEA danach in einem Endzustand befindet.
- Man kann in beiden Fällen von Halten sprechen. Der Akzeptanzvorgang entspricht ja dem (einweg) Lesen eines Bandes, mit Akzeptanz bei Abschluss des Wortlesens in einem Endzustand. --Marc van Woerkom 14:19, 13. Apr 2005 (CEST)
Eventuell wäre hier wie auch beim DEA eine Definition der Zustandsübergangsrelation von Nöten, dann kann man leicht mit ihrer reflexiv-transitiven Hülle argumentieren.
- Reflexiv-transitive Hülle ist nur ein aufgeblähtes Wort für Ableitung/Akzeptanz in endlich (inkl. 0) vielen Schritten. Man benutzt sie eigentlich nur, wenn man die Transitionsfunktion/-relation von der Akzeptanz einzelner Symbole auf die Akzeptanz eines kompletten endlichen Wortes erweitern will. Bei Zweiwegautomaten (2EA) ist sie angebrachter, als bei Einwegautomaten (1EA). --Marc van Woerkom 14:19, 13. Apr 2005 (CEST)
Es sollte erwähnt werden, dass man einen NEA aus einem regulären ausdruck konstruieren kann.
- Die Äquivalenz von endlichen Automaten, regulären Ausdrücken (und MSO Formeln, als Grundlage des Modelcheckings) sollte man schonmal erwähnen. --Marc van Woerkom 14:19, 13. Apr 2005 (CEST)
Ein NEA darf mehr als nur einen Startzustand haben.
- Bei der Übergangsfunktion/relation fehlt die möglichkeit der Epsilon-übergänge.
- Das mag sein, ich würde aber die NEAs und die NEAs mir ε-Übergängen getrennt behandeln. Die mit ε-Übergängen sind noch schwerer zu verstehen als die NEAs schon ohnehin. --Arbol01 14:17, 1. Dez 2004 (CET)
- Ein NEA darf mehr als nur einen Startzustand haben.
- Das wäre mir neu. AFAIK darf ein EA, ob nun NEA oder DEA, nur einen Startzustand bestitzen. Dafür dürfen DEA und NEA aber mehrere Endzustände besitzen. --Arbol01 14:35, 1. Dez 2004 (CET)
--> Regulär AFAIK nicht. Würde meines erachtest auch keinen besonderen Sinn machen.
-
- Kann man so definieren bringt aber auch nix neues, da man von einem Startzustand in die Menge deiner Startzustände (nichtdeterministisch) übergehen könnte, ist das äquivalent in Bezug auf die akzeptierte Sprache. --Marc van Woerkom 14:19, 13. Apr 2005 (CEST)
Was haben Links zu Regulären Ausdrücken aka RegExp hier zu suchen? Meines Erachtens nach: NICHTS.
