Diskussion:Nichtdeterministischer endlicher Automat

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.)

Auf jeden Fall sind bei NEAs \eps - Transitionen NICHT generell erlaubt. \eps -NEAs und NEAs ohne \eps - Transitionen sind zwar äquivalent aber nicht das selbe.

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.

Na dann sei mutig beim Ändern! Stern !? 21:29, 7. Nov 2004 (CET)

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 $\epsilon$-Übergängen getrennt behandeln. Die mit $\epsilon$-Ü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)

Die ganze NEA Konstruktion bringt gegenueber DEAs nichts neues, aber mehere Initialzustaende lassen mitunter elegantere Konstruktionen zu (z.b. schon bei der Vereinigung zweier Sprachen) --Thomas001 20:35, 17. Okt. 2007 (CEST)

Was haben Links zu Regulären Ausdrücken aka RegExp hier zu suchen? Meines Erachtens nach: NICHTS.

Reguläre Ausdrücke und NEAs sind aquivalent.

Fehler im Artikel: Bitte pruefen:

'S \subseteq Q ist eine (endliche) Menge möglicher Startzustände.'

Skript der Vorlesung "Grundlagen Theoretischer Informatik" der Universitaet Bielefeld besagt das nur ein(!) Startzustand existiert.

ich muss dich enttäuschen. bei nea ist es tatsächlich möglich, mehrere startzustände zu definieren. wir hatten das gleiche problem vor kurzem hier kurz diskutiert. gruß --Murkel ^(anmurkeln) 20:32, 17. Dez. 2008 (CET)

Fehler unter Transition als Funktion

Die Funktion muss selbstverständlich von Q x \Sigma -> P(Q) abbilden, nicht nur aus Q. Siehe [1]. Weiß leider nicht, wie ihr das mit den Formeln macht, kann das mal jemand fixen? --Hyrsebrigh 23:20, 11. Mai 2010 (CEST)

Vielen Dank, ist korrigiert. Folgender diff [2] zeigt, wie das in diesem Fall mit den Formeln ging, mehr dazu auf Hilfe:TeX. --Zahnradzacken 01:37, 12. Mai 2010 (CEST)

Beispiel Bild NFA

Das Beispiel Bild zeigt keinen NFA, der laut Definition keine Epsilon Übergäng hat. Es zeigt einen Epsilon NFA. (nicht signierter Beitrag von 141.32.248.115 (Diskussion) 03:46, 18. Jul 2012 (CEST))

Laut welcher Definition? Im Artikel werden mehrere Definitionen verwendet, keine davon besagt, dass ein NFA mit Epsilon-Übergängen "Epsilon NFA" oder "Epsilon-NEA" heiße. In manchen Büchern wird unterschieden, in anderen nicht. Aber das Bild habe ich trotzdem ersetzt. Nicht nur wegen Epsilon, sondern auch weil es viel zu komplex ist. --Zahnradzacken (Diskussion) 17:25, 18. Jul. 2012 (CEST)

Menge der Startzustände

Muss es nicht eine Menge sein, und nicht ein einzelner Startzustand? (nicht signierter Beitrag von 91.19.107.195 (Diskussion) 14:41, 22. Mai 2013 (CEST))

Siehe Nichtdeterministischer endlicher Automat#Mehrere Startzustände? --Zahnradzacken (Diskussion) 23:37, 22. Mai 2013 (CEST)

Mehrere Startzustände machen IMO keinen Sinn. Dagegen kann ein NFA in mehrere Zustände übergehen, das ist ja das Nichtdeterministische dabei. Eine Eingabe wird akzeptiert, wenn sich der Automat nach dem vollständigen Lesen der Eingabe in (mindestens) einem akzeptierenden Zustand befindet. Siehe die korrekte englische Version! DoDi (Diskussion) 12:02, 15. Apr. 2014 (CEST)