Nondeterministic Finite State Machines NFSM（NFA）
Recall FSM
⮚Any state has at most one transition going out with a particular symbol
⮚All FSMs we have studied so far share this property
⮚Because the current state and input symbol uniquely determines the next state
⮚Next state is uniquely given by the current state and the current input
Formal Definition of FSM
o FSM is a 5-tuple where
o S is a finite states set
o $Σ$ is a finite alphabet table, which w=w1w2…wn is an input string that wi in it is a member of Σ
o f is a single value transition function, defines a mapping of $S×∑→S$
o s0 ∈S is an initial state
o Z ∈S is the final states
o The language recognized by M is
NDFA (Nondeterministic Finite Automata)
Are there Nondeterministic FSMs as well？