# 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. – David Richerby Dec 3 '15 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. – Rick Decker Dec 3 '15 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.