Finite Automaton

aka finite state machine, FSM, finite state automaton, FSA

definition a non-deterministic finite automaton is a finite graph whose edges are sets of symbols representing non-deterministic state transitions

an NFA \(M\) may be described by a transition function \(\delta\) that maps a current state and a symbol to a set of reachable next states

definition a deterministic finite automaton is a finite graph whose edges are single symbols representing deterministic state transitions

a DFA \(M\) may be described by a transition function \(\delta\) that maps a current state and a symbol to a single next state

NFAs and DFAs have the same expressive power; a DFA can be converted to an NFA trivially, and an NFA can be converted to a DFA using the powerset construction, which converts "superpositions" of reachable states in the NFA into single states in the DFA