This device, more accurately known as a finite state automaton
, accepts strings by starting in the start state, then hopping from state to state reading a character as indicated by the transition function. Iff
it finishes reading the given string in a state in F, the string is accepted.
These automata also come in a nondeterministic variant,
in which the transition relation is not necessarily a function.