minimal DFA transition function clearification

Question

Statement:

Given any dfa $M$, application of the procedure 'reduce' (see below) yields another dfa $\hat{M}$ such that $M$ and $\hat{M}$ are equivalent. Furthermore $\hat{M}$ is minimal in the sense that there is no other dfa with a smaller number of states that also accepts $L(M)$

First some background information:

The 'reduce' procedure:

Given a dfa $M=\left(Q, \Sigma, \delta, q_{0}, F\right)$, we construct a reduced dfa $\widehat{M}=(\widehat{Q}, \Sigma, \widehat{\delta}, \widehat{q}, \widehat{F})$ as follows.

1. Use procedure mark to generate the equivalence classes, say $\left\{q_{i}, q_{j}, \ldots, q_{k}\right\}$, as described.
2. For each set $\left\{q_{i}, q_{j}, \ldots, q_{k}\right\}$ of such indistinguishable states, create a state labeled $i j \ldots k$ for $\widehat{M}$.
3. For each transition rule of $M$ of the form $$ \delta\left(q_{r}, a\right)=q_{p}, $$ find the sets to which $q_{r}$ and $q_{p}$ belong. If $q_{r} \in\left\{q_{i}, q_{j}, \ldots, q_{k}\right\}$ and $q_{p} \in\left\{q_{l}, q_{m}, \ldots, q_{n}\right\}$, add to $\widehat{\delta}$ a rule $$ \widehat{\delta}(i j \cdots k, a)=l m \cdots n . $$
4. The initial state $\widehat{q}_{0}$ is that state of $\widehat{M}_{\text {}}$ whose label includes the 0 .
5. $\widehat{F}$ is the set of all the states whose label contains $i$ such that $q_{i} \in F$.

A claim in order to prove the statement:

Take any state $q \in Q$ and let $\hat{q}$ denote its equivalence class. For any word $w \in \Sigma^{*}$, it holds that $\delta^{*}(q, w) \in \hat{\delta}^{*}(\hat{q}, w)$. The proof is by induction on the length $n$ of $w$. base case If $n=0$, then $w=\lambda$ and the claim is trivial since $$ \delta^{*}(q, \lambda)=q \in \hat{q}=\hat{\delta}^{*}(\hat{q}, \lambda) . $$ For the induction step assume our claim holds for all strings of length $n-1$ we show that it shows for strings of length $n$. In this case $w=a v$ for some $v$. We know that $$ \begin{array}{rlr} \delta^{*}(q, w) & =\delta^{*}(q, a v) \\ & =\delta^{*}(\delta(q, a), v) & \text { definition of } \delta^{*} \\ & \in \hat{\delta}^{*}(\widehat{\delta(q, a)}, v) & \text { induction hypothesis } \\ & =\hat{\delta}^{*}\left(\hat{\delta}^{}(\hat{q}, a), v\right) \\ & =\hat{\delta}^{*}(\hat{q}, w) \\ \end{array} $$

My question:

In the proof of the claim above, I do not know how we can be sure that

$ \widehat{\delta(q, a)} = \hat{\delta}^{}(\hat{q}, a)$

It seems trivial, but shouldn't it be proven?

Source: Formal languages and automata by Peter Linz, 5th edition (Jones & Bartlett Learning), p. 75

Answer 1

$ \widehat{\delta(q, a)} = \hat{\delta}^{}(\hat{q}, a)$

The equality above is the definition of $\hat\delta$, given $\delta$. Let us paraphrase item 3.

3. For each transition rule of $M$ of the form $$ \delta(q, a)=\delta(q, a), $$ find the sets to which $q$ and $\delta(q, a)$ belong. If $q \in\hat q$ and $\delta(q, a)\in\widehat{\delta(q, a)} $, add to $\widehat{\delta}$ a rule $$ \hat{\delta}(\hat q, a)= \widehat{\delta(q, a)}. $$

---

On the other hand, there is an important question: why is $\delta$ well-defined? Suppose $q_i\in \hat q$ and $q_j\in \hat q$, then $\hat{\delta}(\hat q, a)$ is defined as $\widehat{\delta(q_i,a)}$ as well as $\widehat{\delta(q_j,a)}$. Are $\widehat{\delta(q_i,a)}$ and $\widehat{\delta(q_j,a)}$ the same equivalence class?

This well-defined-ness is a key step in the 'reduce' procedure. I will leave it for you to verify.