Wie funktioniert ein endlicher Automat, wenn er nicht eindeutig ist?

Question

Die Finite State Machine in Frage: -

Wenn ich bei S0 bin und der Eingang ist ein, muss ich wiederholen, um S0 wieder, oder muss ich auf S1 bewegen? Ich weiß nicht, wie ich das feststellen soll. Ist diese Art von FSM überhaupt gültig?

Welche dieser Eingabekombinationen enden im Haltezustand?

• aaabc
• ccc
• bc
• bbc

Answer 1

Dies ist ein NFA (nicht deterministischen Automaten).

Die vom Automaten akzeptiert Worte sind:

• aaabc
• bc

https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton

Answer 2

August

Nur der "aaabc" ist gültig, der Rest hält an, da der FSM "a" als legitimer S0-Eintrag hat.