3 deleted 8 characters in body edited Jun 16 '13 at 17:41 Juho 16.8k55 gold badges4343 silver badges9393 bronze badges For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA. For NFA the situation is complicated as there is no unique minimal NFA in general. Here is an example for the finite language $$\{ ab, ac, bc, ba, ca, cb\}$$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat. (added) This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity. For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA. For NFA the situation is complicated as there is no unique minimal NFA in general. Here is an example for the finite language $$\{ ab, ac, bc, ba, ca, cb\}$$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat. (added) This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity. For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA. For NFA the situation is complicated as there is no unique minimal NFA in general. Here is an example for the finite language $$\{ ab, ac, bc, ba, ca, cb\}$$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat. This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity. 2 reaction to relevant comment and alternative answer edited Jun 16 '13 at 12:47 Hendrik Jan 22.4k2929 silver badges7676 bronze badges For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA. For NFA the situation is complicated as there is no unique minimal NFA in general. Here is an example for the finite language $$\{ ab, ac, bc, ba, ca, cb\}$$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat. (added) This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity. For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA. For NFA the situation is complicated as there is no unique minimal NFA in general. Here is an example for the finite language $$\{ ab, ac, bc, ba, ca, cb\}$$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat. For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA. For NFA the situation is complicated as there is no unique minimal NFA in general. Here is an example for the finite language $$\{ ab, ac, bc, ba, ca, cb\}$$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat. (added) This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity. 1 answered Jun 15 '13 at 18:24 Hendrik Jan 22.4k2929 silver badges7676 bronze badges For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA. For NFA the situation is complicated as there is no unique minimal NFA in general. Here is an example for the finite language $$\{ ab, ac, bc, ba, ca, cb\}$$. The two automata are both state-minimal. The example is from the paper A note about minimal non-deterministic automata by Arnold, Dicky and Nivat. 