We are using Myhill-Nerode Theorem algorithm and we want to prove that this algorithm gives us the minimized DFA.

So let $B$ be the minimized DFA obtained by applying the algorithm to the DFA $A$. We know $L(A)=L(B)$. Now suppose that there is another DFA with fewer states than $B$ such that $L(A)=L(C)$. We run the algorithm for $B\cup C$. Denote the states of $C$ with $c_1,\ldots ,c_n$ and the states of $B$ with $b_1,\ldots , b_m$ where $n<m$.

So at the beginning of the algorithm, all fields $(i, j)$ in the table where either $i$ or $j$ is the accepting state are "marked".

But how do we continue and how do we come to the contradiction?



Browse other questions tagged or ask your own question.