= Finite-state machine
{wiki}
= Finite-state automaton
{synonym}
A <finite-state machine> processes inputs using a <finite set> of <automaton states> and input-dependent <automaton transitions>. An <automaton state> records everything the machine remembers; an <automaton transition> says how that memory changes on the next symbol. A <finite-state machine> may also emit outputs. Here the emphasis is on recognizing a <formal language>: start in a designated <automaton state>, read a <word> from an <alphabet>, and accept exactly when the final <automaton state> is designated accepting.
Finite memory does not impose a maximum input length. A <finite-state machine> can read arbitrarily long <words>, revisiting its <automaton states> indefinitely. The restriction is that the part already read must be compressed into one of finitely many summaries. For <divisibility> by three, a <word> of <binary digits> can describe an enormous <integer>, yet its <congruence class> modulo three is all that the machine needs to retain. Two already-read <words> giving the same <automaton state> behave identically under every subsequent continuation in a <DFA>.
This makes <finite-state machines> useful whenever past details can be forgotten safely: checking whether a sequence of commands follows an allowed order, or recognizing a pattern with a <regular expression>. The beautiful design question is which distinctions about the past matter to the future. <DFA minimization> makes that question precise by merging <indistinguishable states of a deterministic finite automaton>. Both <DFAs> and <NFAs> recognize exactly the <regular languages>.
Back to article page
