Deterministic finite automaton

A deterministic finite automaton has finitely many states and one transition for each state-symbol pair.

For a transition function $\delta :Q\times \Sigma \to Q$, defineThe accepted language is $\{w:\hat{\delta }(q_0,w)\in F\}$.

A state is accessible when some input word takes the initial state to it. Removing inaccessible states preserves the accepted language.

Two states are indistinguishable when every continuation is accepted from both or rejected from both. Distinguishable states admit at least one suffix with different acceptance outcomes.

Indistinguishability is a right-invariant equivalence relation. The quotient has states $[q]$, transition $[q]\mapsto [\delta (q,a)]$, initial state $[q_0]$, and accepting classes represented by accepting states. It accepts the original language and has no two distinct indistinguishable states.

A deterministic automaton is irreducible when every state is accessible and every pair of distinct states is distinguishable.

An irreducible deterministic automaton has the fewest states among deterministic automata for its language and is unique up to isomorphism. Its states are the Myhill--Nerode classes.

The canonical residual automaton of a regular language has its distinct left quotients of a formal language as states, initial state $L$, accepting states those containing the empty word, and letter transition $R\mapsto a^{-1}R$. It is a complete minimal deterministic finite automaton; every other complete minimal deterministic finite automaton for that language is isomorphic to it.

In a minimal deterministic finite automaton accepting a finite language, any state lying on a nonempty directed cycle is the unique rejecting sink state. It cannot reach an accept state, since traversing the cycle arbitrarily many times would produce infinitely many accepted words. Every state reachable from it also rejects every continuation, so minimality forces all such states to be the same state.

For a positive integer $m$, binary strings can be tested for divisibility by $m$ with residue states $0,\dots ,m-1$ and transitionThe initial and accepting residue is zero. For $m=7$, all seven states are reachable and pairwise distinguishable, so this automaton is minimal.

An accessible automaton over one letter consists of a directed tail entering one directed cycle. Its minimal quotient is obtained by merging positions having the same future binary acceptance sequence.

To recognize prescribed parities of several symbol counts, use one state for each tuple of parities. Reading a tracked symbol toggles its coordinate and leaves all other coordinates unchanged. For two tracked symbols this gives four states indexed by ${\mathbb{Z}}_2^2$.

To recognize words having at most $m$ consecutive copies of a symbol, use states $0,1,\dots ,m$ recording the current run length and one rejecting sink. Another symbol resets the run length to zero, while the $(m+1)$st consecutive copy enters the sink.