How do we prove that a particular DFA is minimal?

Question

I guess we need to prove that there is no redundant state, so can we use state elimination and prove that the regular language is minimal?

We could prove that the regular language is minimal by contradiction by assuming each part is unnecessary and proving that it leads to a contradiction.

say we have (a|b|c) and proving that a =/= b =/= c by contradiction.

Answer 1

I would suggest two ways:

• Perform minimization (perhaps by a computer) and show the number of states is the same.
• Check that all states are reachable and distinguishable, i.e.
  1. For any state $s$ there is a word $w \in \Sigma^*$ such that $q_0 \xrightarrow{w} s$.
  2. For each pair $(s_1,s_2)$ of states present a word $w \in \Sigma^*$ such that for $s_1 \xrightarrow{w}s_1'$ and $s_2 \xrightarrow{w}s_2'$ we have $s_1'$ is an accepting state xor $s_2'$ is an accepting state (i.e. $s_1' \in F \iff s_2' \notin F$).

I hope this helps $\ddot\smile$

Answer 2

There is a unique minimal DFA for a given language. To prove that a given DFA is minimal you have to prove that there are no unreachable states that can be eliminated and no nondistinguishable states that can be merged. Wikipedia gives algorithms and references to relevant papers for both in the article on DFA minimization.