[proofplan] An *irreducible* deterministic automaton is one with (i) no inaccessible states and (ii) no two distinct states indistinguishable from each other. Starting from $D$, we perform two reduction moves that each preserve the accepted language and together achieve irreducibility. First, restrict $D$ to its set of accessible states $A \subseteq Q$ to obtain $D^\star$; this removes inaccessible states without changing which words are accepted, since the run on any input word visits only accessible states. Second, quotient $D^\star$ by the indistinguishability equivalence $\sim$ on its state set; this collapses pairs of indistinguishable states, leaving distinguishable quotient classes. The quotient preserves the language, has no inaccessible states (the quotient map is surjective and sends accessible to accessible), and has no indistinguishable distinct states (by construction of $\sim$), so it is irreducible. Setting $I := D^\star / \sim$ gives the required automaton. [/proofplan] [step:Fix notation and the definition of irreducibility] Let \begin{align*} D &= (\Sigma, Q, \delta, q_0, F) \end{align*} be the given deterministic automaton, with extended transition function $\hat{\delta}: Q \times \Sigma^\star \to Q$ defined by $\hat{\delta}(q, \varepsilon) = q$ and $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)$. Recall the following definitions from [Irreducible Automaton](/pages/Irreducible%20Automaton): - A state $q \in Q$ is *accessible* (from the start state) if there exists $w \in \Sigma^\star$ with $\hat{\delta}(q_0, w) = q$. - Two states $p, q \in Q$ are *indistinguishable*, written $p \sim q$, if for every $w \in \Sigma^\star$, \begin{align*} \hat{\delta}(p, w) \in F \iff \hat{\delta}(q, w) \in F. \end{align*} - $D$ is *irreducible* if every state of $D$ is accessible and no two distinct states of $D$ are indistinguishable. We construct an irreducible automaton $I$ with $\mathcal{L}(I) = \mathcal{L}(D)$ in two reduction steps. [/step] [step:Remove inaccessible states by restricting to the accessible subautomaton $D^\star$] Let $A := \{q \in Q : q \text{ is accessible from } q_0\} \subseteq Q$. Then $q_0 \in A$ (take $w = \varepsilon$), and $A$ is closed under $\delta$: if $q \in A$ with $\hat{\delta}(q_0, w) = q$ and $a \in \Sigma$, then $\hat{\delta}(q_0, wa) = \delta(\hat{\delta}(q_0, w), a) = \delta(q, a)$, so $\delta(q, a) \in A$. Hence $\delta$ restricts to a well-defined map $\delta|_{A \times \Sigma}: A \times \Sigma \to A$, and we define \begin{align*} D^\star &:= (\Sigma, A, \delta|_{A \times \Sigma}, q_0, F \cap A). \end{align*} By construction, $D^\star$ is a deterministic automaton, and every state of $D^\star$ is accessible in $D^\star$ (the accessibility witness for $q \in A$ inside $D$ is a word $w$ with $\hat{\delta}(q_0, w) = q$, and the computation of $\hat{\delta}(q_0, w)$ stays inside $A$ by the closure property, so the same $w$ witnesses accessibility of $q$ in $D^\star$). [claim:$\mathcal{L}(D^\star) = \mathcal{L}(D)$] Write $\hat{\delta}^\star$ for the extended transition function of $D^\star$. For every $w \in \Sigma^\star$, since the computation $\hat{\delta}(q_0, w)$ in $D$ visits only accessible states (each intermediate state is of the form $\hat{\delta}(q_0, w')$ for some prefix $w'$ of $w$, hence accessible), and $\delta|_{A \times \Sigma}$ agrees with $\delta$ on $A \times \Sigma$, the two extended transition functions agree on $(q_0, w)$: \begin{align*} \hat{\delta}^\star(q_0, w) &= \hat{\delta}(q_0, w). \end{align*} Therefore \begin{align*} w \in \mathcal{L}(D^\star) \iff \hat{\delta}^\star(q_0, w) \in F \cap A \iff \hat{\delta}(q_0, w) \in F \cap A. \end{align*} The last equivalence uses that $\hat{\delta}(q_0, w) \in A$ always (it is accessible from $q_0$ via $w$), so $\hat{\delta}(q_0, w) \in F \cap A \iff \hat{\delta}(q_0, w) \in F \iff w \in \mathcal{L}(D)$. [/claim] [proof] The argument is contained in the display chain above; the key points are (i) $\hat{\delta}$ stays in $A$ from $q_0$, so restricting has no effect on the computation, and (ii) acceptance in $D^\star$ requires the final state to lie in $F \cap A$, but automatic membership in $A$ makes this equivalent to acceptance in $D$. [/proof] Note that $D^\star$ has no inaccessible states but may still have indistinguishable distinct states. [/step] [step:Quotient $D^\star$ by the indistinguishability relation $\sim$ to form $I$] Define the relation $\sim$ on $A$ as before: $p \sim q$ iff for every $w \in \Sigma^\star$, $\hat{\delta}^\star(p, w) \in F \cap A \iff \hat{\delta}^\star(q, w) \in F \cap A$. We check: *$\sim$ is an equivalence relation.* Reflexivity, symmetry, and transitivity follow immediately from the analogous properties of $\iff$. *$\sim$ is a congruence on $D^\star$*: for $p \sim q$ and $a \in \Sigma$, we have $\delta|_{A \times \Sigma}(p, a) \sim \delta|_{A \times \Sigma}(q, a)$. To see this, take any $w \in \Sigma^\star$; then by applying the definition of $\sim$ to $p, q$ with the test word $aw$, \begin{align*} \hat{\delta}^\star(\delta(p, a), w) = \hat{\delta}^\star(p, aw) \in F \cap A &\iff \hat{\delta}^\star(q, aw) = \hat{\delta}^\star(\delta(q, a), w) \in F \cap A. \end{align*} Thus $\delta(p, a) \sim \delta(q, a)$, establishing the congruence property. *$\sim$ respects the accepting set*: if $p \sim q$ then $p \in F \cap A \iff q \in F \cap A$ (take $w = \varepsilon$ in the definition of $\sim$). These three facts let us define the quotient automaton. Let $\pi: A \to A/{\sim}$ be the quotient map $p \mapsto [p]$ (the $\sim$-equivalence class of $p$). Define \begin{align*} I &:= (\Sigma, A/{\sim}, \bar{\delta}, [q_0], (F \cap A)/{\sim}), \\ \bar{\delta}: A/{\sim} \times \Sigma &\to A/{\sim}, & \bar{\delta}([p], a) &:= [\delta(p, a)], \\ (F \cap A)/{\sim} &:= \{[p] \in A/{\sim} : p \in F \cap A\}. \end{align*} Well-definedness of $\bar{\delta}$: if $[p] = [p']$ (i.e. $p \sim p'$), then $\delta(p, a) \sim \delta(p', a)$ by the congruence property, so $[\delta(p, a)] = [\delta(p', a)]$. Well-definedness of the accepting set: if $[p] = [p']$, then $p \in F \cap A \iff p' \in F \cap A$ by the definition of $\sim$ with $w = \varepsilon$, so the membership $[p] \in (F \cap A)/{\sim}$ does not depend on the representative. Since $\sim$ partitions the finite set $A$ into finitely many classes, $A/{\sim}$ is finite, and $I$ is a finite deterministic automaton. [/step] [step:Verify that the quotient map $\pi$ is a homomorphism and that $\mathcal{L}(I) = \mathcal{L}(D^\star)$] The quotient map $\pi: A \to A/{\sim}$, $p \mapsto [p]$, is a homomorphism of automata from $D^\star$ to $I$: it sends the start state to the start state, \begin{align*} \pi(q_0) &= [q_0], \end{align*} and it commutes with transitions, \begin{align*} \pi(\delta(p, a)) &= [\delta(p, a)] = \bar{\delta}([p], a) = \bar{\delta}(\pi(p), a), \end{align*} and it reflects/preserves acceptance in the sense that $p \in F \cap A \iff \pi(p) \in (F \cap A)/{\sim}$ (by well-definedness of the accepting set together with the fact that $[p] \in (F \cap A)/{\sim}$ iff $p \in F \cap A$). By induction on $|w|$, for every $w \in \Sigma^\star$ and every $p \in A$, \begin{align*} \hat{\bar{\delta}}([p], w) &= [\hat{\delta}^\star(p, w)], \end{align*} where $\hat{\bar{\delta}}$ denotes the extended transition function of $I$. Base: for $w = \varepsilon$, both sides equal $[p]$. Inductive step: for $w = ua$, by the recursive clause, \begin{align*} \hat{\bar{\delta}}([p], ua) &= \bar{\delta}(\hat{\bar{\delta}}([p], u), a) = \bar{\delta}([\hat{\delta}^\star(p, u)], a) = [\delta(\hat{\delta}^\star(p, u), a)] = [\hat{\delta}^\star(p, ua)], \end{align*} using the inductive hypothesis in the second equality, the definition of $\bar{\delta}$ in the third, and the recursive clause of $\hat{\delta}^\star$ in the fourth. Setting $p := q_0$: for every $w \in \Sigma^\star$, \begin{align*} w \in \mathcal{L}(I) &\iff \hat{\bar{\delta}}([q_0], w) \in (F \cap A)/{\sim} \\ &\iff [\hat{\delta}^\star(q_0, w)] \in (F \cap A)/{\sim} \\ &\iff \hat{\delta}^\star(q_0, w) \in F \cap A \\ &\iff w \in \mathcal{L}(D^\star). \end{align*} The third equivalence is well-definedness of the accepting set. Chaining with $\mathcal{L}(D^\star) = \mathcal{L}(D)$, \begin{align*} \mathcal{L}(I) &= \mathcal{L}(D^\star) = \mathcal{L}(D). \end{align*} [/step] [step:Verify that $I$ is irreducible: no inaccessible states and no distinguishable-but-equal pairs] *No inaccessible states in $I$.* Let $[q] \in A/{\sim}$ be any state of $I$. Since $q \in A$, $q$ is accessible in $D^\star$: there exists $w \in \Sigma^\star$ with $\hat{\delta}^\star(q_0, w) = q$. Then \begin{align*} \hat{\bar{\delta}}([q_0], w) &= [\hat{\delta}^\star(q_0, w)] = [q], \end{align*} using the identity proved in the previous step. Hence $[q]$ is accessible in $I$. Since $[q]$ was arbitrary, every state of $I$ is accessible. *No indistinguishable distinct states in $I$.* Suppose $[p], [q] \in A/{\sim}$ and $[p] \sim_I [q]$ in $I$, where $\sim_I$ denotes indistinguishability in $I$: for every $w \in \Sigma^\star$, \begin{align*} \hat{\bar{\delta}}([p], w) \in (F \cap A)/{\sim} &\iff \hat{\bar{\delta}}([q], w) \in (F \cap A)/{\sim}. \end{align*} Substituting $\hat{\bar{\delta}}([p], w) = [\hat{\delta}^\star(p, w)]$ and using well-definedness of the accepting set, the condition rewrites as: for every $w \in \Sigma^\star$, \begin{align*} \hat{\delta}^\star(p, w) \in F \cap A &\iff \hat{\delta}^\star(q, w) \in F \cap A. \end{align*} This is precisely $p \sim q$ in $D^\star$. Hence $[p] = [q]$. So $[p] \sim_I [q] \implies [p] = [q]$, which is exactly the condition "no two distinct states of $I$ are indistinguishable". *Conclusion.* $I$ has no inaccessible states and no distinct indistinguishable states, so $I$ is irreducible. [guided] The proof constructs an irreducible automaton from $D$ by performing two conceptually independent reduction operations — remove unreachable states, then merge equivalent states — and showing each preserves the language. *Why do both reductions preserve the language?* The first, accessibility pruning, removes states that the automaton can never reach from $q_0$. No input word ever causes the automaton to visit those states, so removing them changes nothing about which words are accepted. The second, indistinguishability collapsing, merges states that cannot be distinguished by any input suffix. If two states $p, q$ satisfy "$\hat{\delta}(p, w) \in F \iff \hat{\delta}(q, w) \in F$ for all $w$", then starting from either $p$ or $q$ yields the same acceptance verdict on any continuation. Merging $p$ and $q$ preserves acceptance on every possible trace. *Why do the two reductions commute conceptually but not interchangeably in proof order?* In principle one could quotient first and then restrict to accessible classes. But quotienting is cleaner on a graph without dead states: it simplifies the accessibility analysis of the quotient. We chose to restrict first because $D^\star$ has all states accessible, which makes the quotient $I = D^\star/\sim$ have all classes accessible automatically (via the surjectivity of $\pi$ restricted to the accessible part, which is everything). If we had started by quotienting $D$ directly, we would still have had to check that every class has some accessible representative — not harder in practice but less structured. *The congruence property is the heart of the quotient construction.* For the quotient $\bar{\delta}$ to be well-defined, we need: "$p \sim q$ implies $\delta(p, a) \sim \delta(q, a)$". Why does this hold? Because $\sim$ is defined by "all suffixes give the same acceptance verdict". Reading one letter $a$ and then testing on suffix $w$ is the same as testing on suffix $aw$ directly. So if $p \sim q$, taking any $a$-successor, the pair $(\delta(p, a), \delta(q, a))$ satisfies the defining condition (test with $w$ to check $\hat{\delta}(\delta(p, a), w) \in F \iff \hat{\delta}(\delta(q, a), w) \in F$; but this equals $\hat{\delta}(p, aw) \in F \iff \hat{\delta}(q, aw) \in F$, which holds because $p \sim q$ and $aw \in \Sigma^\star$). *Why is the quotient irreducible?* Accessibility is preserved automatically by the quotient map being surjective from $A$ to $A/\sim$ and intertwining transitions. Irreducibility's second requirement — distinguishability — is immediate from the quotient construction: $[p] \sim_I [q]$ unpacks to $p \sim q$ in $D^\star$, which means they are in the same class, i.e., $[p] = [q]$. The quotient construction deliberately glues together indistinguishable states so that the quotient has none. *Minimality.* This construction in fact produces the *minimum-state* automaton for the language, not merely *some* irreducible automaton, and the uniqueness theorem [Uniqueness of the Irreducible Automaton](/theorems/1798) makes the adjective "the minimum" meaningful by showing all irreducible automata for the same language are isomorphic. But for the existence claim we are proving here, minimality is a bonus; the theorem asks only for existence. [/guided] [/step] [step:Assemble the conclusion] Given the arbitrary deterministic automaton $D$, we constructed $D^\star$ by restricting to accessible states, then $I := D^\star/\sim$ by quotienting by indistinguishability. We verified $\mathcal{L}(I) = \mathcal{L}(D^\star) = \mathcal{L}(D)$ and that $I$ is irreducible. This exhibits the required equivalent irreducible automaton. Since $D$ was arbitrary, every deterministic automaton has an irreducible equivalent, completing the proof. [/step]