Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
deterministisch oder nicht?
Es sind hier vier verschiedene Automaten dargestellt. Und die Frage ist ob die deterministisch sind oder nicht. Ist bei deterministischen Automaten so, dass von JEDEN Zustand kann man in JEDER anderer Zustand veschseln oder ist es nur so, dass man kann von jeder Zustand in anderen definierten Zustand veschseln?
“Ein deterministischer endlicher Automat […] ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt.”
Zitat: http://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat
“Ein nichtdeterministischer endlicher Automat […] ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt.”
Zitat: http://de.wikipedia.org/wiki/Nichtdeterministischer_endlicher_Automat
Das bedeutet:
hast du einen Zustand, eine Eingabe und genau einen möglichen Nachfolgezustand => deterministisch
hast du einen Zustand, eine Eingabe und mehr als ein möglichen Nachfolgezustand => nicht deterministisch
Wenn sich ein Automat entscheiden könnte was sein Nachfolgezustand ist, ist er nicht deterministisch.
1 Like