0
$\begingroup$

My idea is that the number of states in the minimum DFA is equal to the number of equivalent states. So, if there exists another minimum DFA, then it must have different equivalent states than the previous DFA which is not possible.

How do I formally prove this?

EDIT: Maybe something like "since two states are equivalent, they are semantically equivalent and hence, they can't be equivalent and different at the same time" might do if written formally?

$\endgroup$
  • 3
    $\begingroup$ This proof is contained in all textbooks on the matter. If it has been assigned as homework to you, you should give it a serious try on your own. What have you tried and where have you gotten stuck? $\endgroup$ – Raphael Sep 5 '16 at 13:37
  • $\begingroup$ @Raphael I've already written what I've tried in the question details. It is sort of a contradiction proof. I'm wondering if someone could help me phrase it properly as an answer. $\endgroup$ – aste123 Sep 7 '16 at 5:41
  • $\begingroup$ To those who are downvoting the question, consider that I've mentioned a contradiction proof (informally) in the question details. My question is mostly focused on what minor details may be added to it to make it complete. $\endgroup$ – aste123 Sep 7 '16 at 5:43
  • $\begingroup$ Yes, you gave a rough idea. But have you tried making it rigorous? That's what this exercise is supposed to train you in, among other things. $\endgroup$ – Raphael Sep 7 '16 at 9:24
1
$\begingroup$

Suppose that we are given a regular language $L$ and a DFA ${\cal A} = (Q,q_0,F,\delta)$. Denote the equivalence classes of the Myhill–Nerode relation of $L$ by $S_1,\ldots,S_m$. For each state $q \in Q$, define $L_q = \{w \in \Sigma^* : \delta(q_0,w) = q\}$. From the definition of the Myhill–Nerode relation it follows that each $L_q$ is a subset of some $S_i$.

The Myhill–Nerode theorem shows that there is a DFA with $m$ states, so suppose that ${\cal A}$ has $m$ states. From our comment above it follows that each $L_q$ equals some $S_i$. Rename the states so that $S_i = L_i$ (so now $Q = \{1,\ldots,m\}$). We now read off all the other data of ${\cal A}$:

  1. The starting state $q_0$ is the one whose language contains the empty word $\epsilon$, that is, it is determined by the condition $\epsilon \in S_{q_0}$.

  2. A state $i$ is accepting if $S_i \subseteq L$, and rejecting if $S_i \subseteq \overline{L}$ (it follows from the definition of the Myhill–Nerode relation that these are the only two possibilities).

  3. Let $w_i$ be an arbitrary word in $S_i$, and let $\sigma \in \Sigma$. Then $\delta(i,\sigma) = j$ if $w_i\sigma \in S_j$. Again, the definition of the Myhill–Nerode relation shows that the choice of $w_i$ doesn't matter.

After renaming the states of ${\cal A}$ in a canonical way, we read off ${\cal A}$ from the Myhill–Nerode relation of $L$. It follows that all minimial DFAs for $L$ are equivalent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.