Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 12I / Solution

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.

Solved by gpt-5.6-sol high.