[proofplan] Let $f: D \to D'$ be a homomorphism between deterministic automata. The strategy is to transfer acceptance from $D$ to $D'$ letter by letter along $f$: an induction on word length shows $f(\hat{\delta}(q, w)) = \hat{\delta}'(f(q), w)$ for every state $q$ and every word $w \in \Sigma^\star$, using the single-step compatibility $f(\delta(q, a)) = \delta'(f(q), a)$ built into the definition of a homomorphism. Applying this identity at the start state $q_0$ and combining with the start-state and final-state conditions $f(q_0) = q_0'$ and $q \in F \iff f(q) \in F'$ yields the biconditional $w \in \mathcal{L}(D) \iff w \in \mathcal{L}(D')$, hence $\mathcal{L}(D) = \mathcal{L}(D')$. [/proofplan] [step:Fix notation for the two automata and the homomorphism] Write \begin{align*} D &= (\Sigma, Q, \delta, q_0, F), & D' &= (\Sigma, Q', \delta', q_0', F'), \end{align*} so $D$ and $D'$ share a common alphabet $\Sigma$. A [homomorphism of deterministic automata](/theorems/???) is a map \begin{align*} f: Q &\to Q' \end{align*} satisfying the three defining conditions \begin{align*} f(q_0) &= q_0', \\ f(\delta(q, a)) &= \delta'(f(q), a) \qquad \text{for all } q \in Q,\ a \in \Sigma, \\ q \in F &\iff f(q) \in F' \qquad \text{for all } q \in Q. \end{align*} Let $\hat{\delta}: Q \times \Sigma^\star \to Q$ and $\hat{\delta}': Q' \times \Sigma^\star \to Q'$ be the [extended transition functions](/theorems/???) of $D$ and $D'$, defined recursively by $\hat{\delta}(q, \varepsilon) = q$ and $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)$, and likewise for $\hat{\delta}'$. Recall that $w \in \mathcal{L}(D) \iff \hat{\delta}(q_0, w) \in F$, and $w \in \mathcal{L}(D') \iff \hat{\delta}'(q_0', w) \in F'$. [/step] [step:Prove the compatibility identity $f(\hat{\delta}(q, w)) = \hat{\delta}'(f(q), w)$ by induction on $|w|$] [claim:For every $q \in Q$ and every $w \in \Sigma^\star$, $f(\hat{\delta}(q, w)) = \hat{\delta}'(f(q), w)$] We induct on the length $|w|$ of the word. *Base case*, $|w| = 0$, so $w = \varepsilon$. By definition of the extended transition functions, $\hat{\delta}(q, \varepsilon) = q$ and $\hat{\delta}'(f(q), \varepsilon) = f(q)$. Hence \begin{align*} f(\hat{\delta}(q, \varepsilon)) &= f(q) = \hat{\delta}'(f(q), \varepsilon). \end{align*} *Inductive step.* Fix $n \geq 0$ and assume the identity holds for every word of length $n$. Let $w \in \Sigma^\star$ have length $n + 1$; write $w = u a$ with $u \in \Sigma^\star$ of length $n$ and $a \in \Sigma$. By the recursive definition of $\hat{\delta}$, \begin{align*} \hat{\delta}(q, ua) &= \delta(\hat{\delta}(q, u), a). \end{align*} Applying $f$ and using the single-letter compatibility condition $f(\delta(q', a)) = \delta'(f(q'), a)$ at the state $q' := \hat{\delta}(q, u) \in Q$ gives \begin{align*} f(\hat{\delta}(q, ua)) &= f(\delta(\hat{\delta}(q, u), a)) = \delta'(f(\hat{\delta}(q, u)), a). \end{align*} By the inductive hypothesis applied to $u$ (which has length $n$), $f(\hat{\delta}(q, u)) = \hat{\delta}'(f(q), u)$. Substituting, \begin{align*} f(\hat{\delta}(q, ua)) &= \delta'(\hat{\delta}'(f(q), u), a) = \hat{\delta}'(f(q), ua), \end{align*} where the last equality is the recursive definition of $\hat{\delta}'$ applied at $f(q)$ with word $ua$. This completes the inductive step, and hence the claim. [/claim] [proof] See the inductive argument stated in the claim. [/proof] [/step] [step:Specialise to the start state $q_0$ and use $f(q_0) = q_0'$] Apply the identity just proved with $q := q_0$. For every $w \in \Sigma^\star$, \begin{align*} f(\hat{\delta}(q_0, w)) &= \hat{\delta}'(f(q_0), w) = \hat{\delta}'(q_0', w), \end{align*} where the second equality uses the start-state condition $f(q_0) = q_0'$ from the definition of a homomorphism. [/step] [step:Combine with the final-state condition to obtain $\mathcal{L}(D) = \mathcal{L}(D')$] Fix $w \in \Sigma^\star$. We chain three biconditionals: \begin{align*} w \in \mathcal{L}(D) &\iff \hat{\delta}(q_0, w) \in F && \text{(definition of } \mathcal{L}(D)\text{)} \\ &\iff f(\hat{\delta}(q_0, w)) \in F' && \text{(final-state condition } q \in F \iff f(q) \in F'\text{)} \\ &\iff \hat{\delta}'(q_0', w) \in F' && \text{(previous step)} \\ &\iff w \in \mathcal{L}(D'). && \text{(definition of } \mathcal{L}(D')\text{)} \end{align*} The second biconditional applies the final-state condition at the state $q := \hat{\delta}(q_0, w) \in Q$. The third substitutes the identity from the previous step. Since this chain of biconditionals holds for every $w \in \Sigma^\star$, we conclude $\mathcal{L}(D) = \mathcal{L}(D')$. [guided] The result is a clean statement about how the structure of a homomorphism interacts with the acceptance condition. To prove it, we need to show that every word is accepted by $D$ precisely when it is accepted by $D'$. Acceptance is decided by a single query: does $\hat{\delta}(q_0, w) \in F$? So the question reduces to: can we transport the state $\hat{\delta}(q_0, w)$ across $f$ to $\hat{\delta}'(q_0', w)$ in $D'$? The homomorphism property is designed exactly to make this transport work. The single-letter compatibility $f(\delta(q, a)) = \delta'(f(q), a)$ says: "one letter of $D$-dynamics, then apply $f$" equals "apply $f$, then one letter of $D'$-dynamics". The natural induction extends this from one letter to any word: "any number of letters of $D$-dynamics, then apply $f$" equals "apply $f$, then the same letters of $D'$-dynamics". Formally, we prove by induction on $|w|$ that \begin{align*} f(\hat{\delta}(q, w)) = \hat{\delta}'(f(q), w) \qquad \text{for all } q \in Q,\ w \in \Sigma^\star. \end{align*} The base case $w = \varepsilon$ holds because both sides collapse to $f(q)$ by definition of the extended transition function. The inductive step for $w = ua$ reduces the length-$(n+1)$ case to the length-$n$ case by peeling off the last letter: first use the recursive definition $\hat{\delta}(q, ua) = \delta(\hat{\delta}(q, u), a)$, then apply the single-letter compatibility at $\hat{\delta}(q, u)$ to push $f$ through, then apply the inductive hypothesis to $u$, and finally reassemble using the recursive definition of $\hat{\delta}'$. With this identity in hand, we apply it at $q = q_0$. The start-state axiom $f(q_0) = q_0'$ converts $\hat{\delta}'(f(q_0), w)$ to $\hat{\delta}'(q_0', w)$. Hence \begin{align*} f(\hat{\delta}(q_0, w)) = \hat{\delta}'(q_0', w). \end{align*} Now we relate this to membership in the two languages. The final-state axiom says $q \in F \iff f(q) \in F'$. Applied at $q = \hat{\delta}(q_0, w)$, this reads $\hat{\delta}(q_0, w) \in F \iff f(\hat{\delta}(q_0, w)) \in F'$. But the left-hand side is the definition of $w \in \mathcal{L}(D)$ and the right-hand side equals $\hat{\delta}'(q_0', w) \in F'$ by the identity we just derived — which is the definition of $w \in \mathcal{L}(D')$. The biconditional is complete. All three axioms of a homomorphism are used in the argument: the single-letter compatibility drives the induction, the start-state axiom anchors it at $q_0$, and the final-state axiom converts state membership to language membership. None is redundant: without the start-state axiom we would compare $w \in \mathcal{L}(D')$ against acceptance from $f(q_0)$ rather than $q_0'$, and without the final-state axiom there would be no connection between $F$ and $F'$ at all. [/guided] [/step]