Frage von VaNiFrEaK, 23

Ist ein Akzeptor immer ein deterministischer Automat (Informatik)?

Ich habe gehört, dass es deterministische und nicht-deterministische Automaten gibt. Ein Akzeptor ist ein Automat OHNE Ausgabe und hat aber dafür einen Endzustand. Meine Frage: Muss ein Akzeptor immer ein deterministischer Automat sein oder kann er auch nicht-deterministisch sein?

Antwort
von Zuck3r, 23

Gemäß der definition kann auch ein nfa ein Akzeptor sein. Ein NFA und ein DFA können beide genau einen Endzustand haben. Der Unterschied ist, dass du bei einem NFA aufgrund des akzeptieren Wortes nicht unbedingt den Weg im Automaten eindeutig erkennen kannst.

Kommentar von VaNiFrEaK ,

Vielen Dank für die schnelle Antwort :) Und Sie sind sich da wirklich ganz sicher? Ich halte nämlich einen Vortrag drüber :D

Kommentar von Zuck3r ,

Relativ ja. Die Vorlesung ist schon nen halbes Jahr her.

Aber das ist der einzige mit bekannte Unterschied zwischen NFA und DFA. Eben dass der Weg nicht genau bestimmbar ist.

Und wenn ich mal eben google bemühe, finde ich zb dashier: https://de.wikipedia.org/wiki/Automat_(Informatik)

Da gibt es keine Einschränkung, dass ein Akzeptor nur ein NFA/DFA sein muss. Also würde ich sagen ja auch ein NFA ist, bzw kann ein Akzeptor sein

Kommentar von VaNiFrEaK ,

Alles klar. Dann vertraue ich Ihnen mal :) Im Internet habe ich nämlich die Definition "Ein Akzeptor ist ein deterministischer Automat.." gesehen. Deshalb war ich mir nicht sicher.

Kommentar von Zuck3r ,

Das kann natürlich auch sein, dass jeder das anders definiert, ist bei uns teilweise vom Dozenten abhängig. Dann sollte man vielleicht die Unterlagen des Fachs/Moduls zu Rate ziehen.

Aber man kann theoretisch aus einem NFA auch einfach einen DFA machen.

Antwort
von Schachpapa, 14

Man kann jeden NFA in einen DFA umwandeln.

https://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten