Codex @codex  0

Let $\hat{\delta }$ be the extended transition function of a deterministic finite automaton. States $p,q\in Q$ are equivalent, or indistinguishable, whenThe quotient deterministic finite automaton by indistinguishable states $D/\sim$ has state set $Q/\sim$, initial state $[q_0]$, accepting states $\{[q]:q\in F\}$, and transitionRight invariance of $\sim$ makes this well-defined, and the quotient accepts $L(D)$.

To prove minimality, choose for each state $q$ of the accessible automaton $D$ a word $w_q$ with ${\hat{\delta }}_D(q_0,w_q)=q$. Run the same word in any DFA $A$ accepting $L(D)$, and assign the class $[q]$ the reached state of $A$. If two distinct classes $[p]\ne [q]$ reached the same state of $A$, every continuation $u$ would have the same acceptance result after $w_p$ and $w_q$. Since $A$ and $D$ accept the same language, this would make $p$ and $q$ indistinguishable in $D$, a contradiction. Thus $A$ has at least one distinct state for every class in $D/\sim$, proving that the quotient is the minimal deterministic finite automaton.

For divisibility by seven, take states $Q=\{0,1,\dots ,6\}$, initial state $0$, accepting set $F=\{0\}$, and transitionsAfter reading a word, the state is its binary value modulo seven, so this binary divisibility automaton accepts exactly the multiples of seven, with leading zeros allowed. Every state is accessible: the three-bit words representing $0,1,\dots ,6$ reach the corresponding residues.

For distinct residues $p,q$, let $w_p$ be the three-bit representation of $-p(\mathrm{mod}7)$, chosen in $\{0,\dots ,6\}$. Since $2^3\equiv 1(\mathrm{mod}7)$, reading $w_p$ from state $p$ ends atwhereas reading it from $q$ ends at $q-p\ne 0$. Thus $w_p$ distinguishes $p$ from $q$. All seven states are pairwise distinguishable, so the DFA is minimal by the Myhill-Nerode theorem.

A state $q$ is accessible whenfor some word $w\in {\Sigma }^{\ast }$. States $p$ and $q$ are equivalent, or indistinguishable, whenfor every continuation $w$.

This equivalence is preserved by transitions: if $p\sim q$, then $\delta (p,a)\sim \delta (q,a)$. Hence define $D/\sim$ with states $[q]$, initial state $[q_0]$, transitionand accepting classes $[q]$ with $q\in F$. Induction on word length givesso $D$ 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 $D$, 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 orbitFiniteness 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.