How to prove that a minimal DFA is actually minimal? The book I'm reading has the following proof, but there are parts I don't understand:
…to show that $\widehat{M}$ is minimal, is harder. Suppose $\widehat{M}$ has states $\{p_0, p_1, p_2, …, p_m\}$, with $p_0$ the initial state. Assume that there is an equivalent dfa $M_1$, with transition function $\delta_1$ and initial state $q_0$, equivalent to $\widehat{M}$, but with fewer states. Since there are no inaccessible states in $\widehat{M}$, there must be distinct strings $w_1, w_2, …, w_m$ such that
$$
\widehat{\delta}^∗(p_0,w_i)=p_i, i=1,2,…,m
$$
- The last equation seems to say that each state in a minimal DFA must not be unreachable. However, it appears that there may be multiple strings leading to each state. One of the minimal DFAs introduced in the book is as follows. In fact, the methods for arriving at vertex $2$ are $00, 10, 1000$, etc.
The proof that follows is as follows.
But since $M_1$ has fewer states than $\widehat{M}$, there must be at least two of these strings, say $w_k$ and $w_l$, such that
$$
\delta_1^∗(q_0,w_k)=\delta_1^∗(q_0,w_l)
$$
Since $p_k$ and $p_l$ are distinguishable, there must be some string $x$ such that $\widehat{\delta}^∗(p_0,w_kx)=\widehat{\delta}^∗(p_k,x)$ is a final state, and $\widehat{\delta}^*(q_0,w_lx)=\widehat{\delta}^∗(p_l,x)$ is a nonfinal state (or vice versa). In other words, $w_kx$ is accepted by $\widehat{M}$ and $w_lx$ is not.
- What I don't understand is that the equation above seems to hold true for $\widehat{M}$ as well as $M_1$. As mentioned earlier, the vertex 2 in the figure above shows this fact. That is, I don't think that equation applies only to $M_1$. This is because, starting from vertex $0$, we can reach the same next vertex $2$ through different strings such as $00,10,1000$, etc.
- So, $\widehat{\delta}^*(p_0,w_k)=\widehat{\delta}^*(p_0,w_l)$ for some strings $w_k$ and $w_l$ can be hold to $\widehat{M}$ too.
The proof continues
But note that
$$
\begin{align}
\delta_1^*(q_0,w_kx)&=\delta_1^*(\delta_1^*(q_0,w_k),x)\\
&=\delta_1^*(\delta_1^*(q_0,w_l),x)\\
&=\delta_1^*(q_0,w_lx).
\end{align}
$$
Thus, $M_1$ either accepts both $w_kx$ and $w_lx$ or rejects both, contradicting the assumption that $\widehat{M}$ and $M_1$ are equivalent. This contradiction proves that $M_1$ cannot exist.
This proof was taken from the book 'An Introduction to Formal Languages and Automata 6th'(978-1284077247).
Could you explain the proof in detail so that it is easy to understand? I don't understand the part that continues from the first quoted part to the second quoted part.
Best Answer
I think I understood it after reading it a few more times.
Because $\widehat{M}$ is a minimal DFA, for every state, there must be distinct strings leading up to each state. The following equation tells this fact. Of course, there can be multiple strings leading up to each state, but we are paying attention to the fact that the string arriving in each state is distinct for each state:
Since $M_1$ has fewer states than $\widehat{M}$, some of those strings will arrive in the same state. For example, in the figure attached to the question, if the string is $00$, it arrives at state $2$, and if the string is $01$, it arrives at state $4$. These strings arrive in different states and are distinct strings:
Suppose state $4$ disappears and the transition function is modified as appropriate, so that if the string is $01$, we arrive at state $2$. Then, if the string is $00$ or $01$, they arrive in the same state, that is state $2$:
Also, the following needs to be fixed($q_0$ -> $p_0$). It appears to be a typo:
to