Finite-state machine 2026-10-14
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.
Suppose a path took to a state . Part (i) implies that no accept state is reachable from either or . Thus every possible continuation is rejected from both states, so and are indistinguishable states of a deterministic finite automaton. Distinct indistinguishable states cannot occur in a minimal deterministic finite automaton. Therefore , and there is no path from to any other state.
A state is accessible when
for some word . States and are equivalent, or indistinguishable, when
for every continuation .
This equivalence is preserved by transitions: if , then . Hence define with states , initial state , transition
and accepting classes with . Induction on word length gives
so and its quotient deterministic finite automaton by indistinguishable states accept the same language. If two quotient states were equivalent, their representatives would be equivalent in , so the classes would be equal. Thus no two distinct quotient states are equivalent.
For the unary alphabet, accessibility means that all states occur on the orbit
Finiteness makes this orbit a directed tail entering a directed cycle. The quotient retains exactly one accepting state and merges precisely those positions having the same future acceptance pattern.
More explicitly, if the unique accepting state lies before the cycle, every state after it can never reach acceptance and these states collapse to one rejecting sink. The minimal diagram is then a directed chain from the initial state through the unique accepting state and onward to that sink, which has a self-loop.
If the accepting state lies on the cycle, all cycle states are distinct because their next visits to the accepting state occur in different residue classes modulo the cycle length. Any remaining tail is a chain feeding the cycle. In a minimal diagram with a nonempty tail, the accepting state is the cycle vertex immediately preceding the entry vertex; otherwise the final tail state has the same future acceptance sequence as a cycle state and would be merged. A pure cycle with one accepting vertex is also possible. These are exactly the minimal accessible unary DFAs with one accepting state.