0
$\begingroup$

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?

If so, what about this case?

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Dec 3 '15 at 20:11
  • $\begingroup$ 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. $\endgroup$ – Rick Decker Dec 3 '15 at 20:39
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.