T
T
token2012-06-21 11:29:55
JavaScript
token, 2012-06-21 11:29:55

Minimizing DFA using Hopcroft's algorithm?

Hello experts!
So I constructed a DFA from an NFA constructed from a regular expression, the task was to minimize the DFA using Hopcroft's algorithm. My DFA is represented as a JSON object and looks like this:

{
  0: [{
    from: 97,
    to: 97,
    shift: 1
  }],
  1: [{
    from: 97,
    to: 97,
    shift: 3
  }, {
    from: 98,
    to: 98,
    shift: 2
  }],
  2: [{
    from: 98,
    to: 98,
    shift: 4
  }],
  3: [{
    from: 97,
    to: 97,
    shift: 3
  }, {
    from: 98,
    to: 98,
    shift: 4
  }],
  4: [{
    from: 98,
    to: 98,
    shift: 4
  }]
}

The keys of the object, respectively, are the numbers of the states (0 is the starting state), each state is an array of objects, each of which is an interval of characters (from, to) and the state to which the transition must be made (shift).
I would like to get the minimum DFA from the presented. One method is to construct a table of pairs of states using Hopcroft's algorithm, then go through the table and find identical states (those that go to the same states for the same symbols). I don't fully understand how minimization works in Hopcroft's algorithm, but what I understand makes me think that it can be done more simply.
So my minimization algorithm is as follows:
1. For each state (denoted as 0, 1, 2, 3, 4 in my example), you need to get a unique hash identifying it (for example, for state 0 it will be: from=97,to=97,shift=1, for state 1 it will be: from=97,to=97,shift=3&from=98,to=98,shift=2 and so on...)
2. Compare the received hashes and if we find two identical, then the states for which they were generated can be glue together (merge). In my example, the hash of state 2 will be: from=98&shift=4&to=98, and the hash of state 4 will be: from=98&shift=4&to=98, they are the same, so we can glue them together to get a new state 5, after that DFA will be look like this:
{
  0: [{
    from: 97,
    to: 97,
    shift: 1
  }],
  1: [{
    from: 97,
    to: 97,
    shift: 3
  }, {
    from: 98,
    to: 98,
    shift: 5
  }],
  3: [{
    from: 97,
    to: 97,
    shift: 3
  }, {
    from: 98,
    to: 98,
    shift: 5
  }],
  5: [{
    from: 98,
    to: 98,
    shift: 5
  }]
}

3. Repeat steps 1, 2 until we have no states with matching hashes, for example, the next step is to merge states 1 and 3 to create a new state 6, which will give us the following DFA:
{
  0: [{
    from: 97,
    to: 97,
    shift: 6
  }],
  6: [{
    from: 97,
    to: 97,
    shift: 6
  }, {
    from: 98,
    to: 98,
    shift: 5
  }],
  5: [{
    from: 98,
    to: 98,
    shift: 5
  }]
}

4. There are no more identical states, so we are done.
Now the actual question ... is this bicycle invented by me similar in the result (and general meaning) to Hopcroft's algorithm?

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question