# Termination of Moore's algorithm to minimize deterministic automata

I use Moore's algorithm to minimize DFA as concluded below.

1. We start with the complete graph with vertices Q and edges E = { {p, q} | p = q ∈ Q }
2. We mark all edges {p, q} ∈ E with p ∈ F and q ∈ F
3. As long as there exist marked edges in E, we repeat the following procedure. We choose some marked edge {p , q } ∈ E. Then we mark all unmarked edges {p, q} ∈ E with {p , q } = {p · a, q · a} for some a ∈ Σ. Afterwards we remove the edge {p , q } from E.
4. All marked edges are eventually removed.

Then I guess a new minimal automata is obtained by joining the states linked by the remaining unmarked edges. Is it true?

States: {1, 2, 3}
Alphabet: {a, b}
Start: 1
Final: {3}
Transition: {(1, a, 2), (2, b, 3)}


By Moore's algorithm, at the end of loop we will have one unmarked edge between state 1 and 2. As my guess above, the next step is joining both states. But the result doesn't make sense.

• I'm not sure why you're guessing. An algorithm is, by definition, a description of exactly what needs to be done. If you want to know what an algorithm does, read the algorithm. Dec 3, 2015 at 20:11
• This isn't Moore's algorithm, so it's no surprise that your result doesn't make sense. Go back to your notes and carefully compare the algorithm with what you've written. Dec 3, 2015 at 20:39

Most minimization algorithms assume automata to be complete s.t. for every state p and alphabet a, there is a transition where (p, a, q). Hence, for the case, we need to add one more state as a sink state. The DFA becomes:

States: {1, 2, 3, 4}
Alphabet: {a, b}
Start : 1
Final : {3}
Transition :
{(1, a, 2), (1, b, 4), (2, a, 4), (2, b, 3), (3, a, 4), (3, b, 4),
(4, a, 4), (4, b, 4)}


By Moore's algorithm:

Picking edge(3,4) causes we mark edge(2,1) and edge(2,4) by b-transition.

Picking edge(2,4) causes we mark edge(1,4) by a-transition.

Now we don't have any unmarked edges left. Hence, no states has to be joined.