proof DFA defines same language as minimal DFA

Question

Given a $DFA = (Q, \Sigma, \delta, q_s, F)$ and a minimal $DFA_{MIN} = (Q_{MIN}, \Sigma, \delta_{MIN}, q_{s_{MIN}}, F_{MIN})$ where

1. $Q_{MIN} = \{Q_i \in \mathcal{P}(Q) \mid \forall p,q \in Q_i:p \text{ and } q \text{ are indistinguishable states}\}$ is a partition of $Q$
2. $F_{MIN} = \{S \in Q_{MIN}\mid S \cap F \neq \emptyset\}$
3. $q_{s_{MIN}} = Q_i$ for which $q_s \in Q_i$
4. $\forall a \in \Sigma : \delta_{MIN}(Q_i,a) = Q_j \Leftrightarrow \exists q \in Q_i : \delta(q,a) \in Q_j$.

Proof that $L_{DFA} = L_{DFA_{MIN}}$.

I can intuitively see that this is correct, but I find it hard to prove this neatly. The closest I got, was something like this:

1. First of all try to prove $s \in L_{DFA} \Rightarrow s \in L_{DFA_{MIN}}$. Because $s \in L_{DFA}$, there exists a series of states $(t_1,t_2,\ldots,t_n)$ in the $DFA$ that accepts $s$. In other words: $t_1 = q_s$, $t_n \in F$ and $t_{i+1} = \delta(t_i,a)$ for some $a \in \Sigma$. Now we transform states $t_i \in Q$ to states $T_i \in Q_{MIN}$ so that $t_i \in T_i$ (every $q \in Q$ has a corresponding $p \in Q_{MIN}$, because that last one is a partition). Now $q_s = t_1 \in T_1$, thus $q_{s_{MIN}} = T_1$. Also $t_n \in T_n$ and $t_n \in F$, which makes that $T_n \cap F \neq \emptyset$ and thus $T_n \in F_{MIN}$. Eventually $t_{i+1} \in T_{i+1}$, thus $\delta(t_i,a) \in T_{i+1}$, which makes that $T_{i+1} = \delta_{MIN}(T_i,a)$. QED
2. Now prove $s \in L_{DFA_{MIN}} \Rightarrow s \in L_{DFA}$. $\ldots$

I have been thinking about it for so long that I can't find any way anymore to prove the second part. I also start to doubt more and more about the first part of my proof.

Thanks in advance...

Answer 1

Suppose that $w\in L_{DFA_{MIN}}$, say $w=a_1\ldots a_n$, where each $a_k\in\Sigma$. Then there is a sequence $\langle T_0,\ldots,T_n\rangle$ of states in $Q_{MIN}$ such that $T_0=q_{s_{MIN}}$, $T_n\in F_{MIN}$, and $\delta_{MIN}(T_k,a_{k+1}=T_{k+1})$ for $k=0,\ldots,n-1$.

Since $T_n\in F_{MIN}$, there is a $q_n\in T_n\cap F$. Suppose that $q\in T_n$; $q$ and $q_n$ are indistinguishable, and $\delta^*(q_n,\epsilon)\in F$, so $\delta^*(q,\epsilon)\in F$. (Here $\delta^*$ is the usual extension of $\delta$ to $\Sigma^*$.) Thus, $T_n\subseteq F$. Now $T_n=\delta_{MIN}(T_{n-1},a_n)$, so there is a $q_{n-1}\in T_{n-1}$ such that $\delta(q_{n-1},a_n)\in T_n\subseteq F$. Similarly, $T_{n-1}=\delta_{MIN}(T_{n-2},a_{n-1})$, so there is a $q_{n-2}\in T_{n-2}$ such that $\delta(q_{n-2},a_{n-1})\in T_{n-1}$. The states $q_{n-1}$ and $\delta(q_{n-2},a_{n-1})$ are indistinguishable, and $\delta(q_{n-1},a_n)\in F$, so $\delta^*(q_{n-2},a_{n-1}a_n)\in F$. In this fashion we can recursively show the existence of $q_k\in T_k$ for $k=n,n-1,\ldots,0$ such that $\delta^*(q_k,a_{k+1}\ldots a_n)\in F$. In particular, $\delta^*(q_0,w)\in F$. Finally, $q_0\in T_0=q_{s_{MIN}}$, so $q_0$ and $q_s$ are indistinguishable, and hence $\delta^*(q_s,w)\in F$, i.e., $w\in L_{DFA}$. Thus, $L_{DFA_{MIN}}\subseteq L_{DFA}$.