Class HopcroftMinimizer

java.lang.Object
  extended byHopcroftMinimizer
All Implemented Interfaces:
Minimizer

public class HopcroftMinimizer
extends java.lang.Object
implements Minimizer

A class implementing Hopcroft's minimization algorithm to minimize a DFA. The time complexity is O(n log(n)).


Field Summary
static boolean verbose
          A boolean flag allowing to set a verbose mode.
 
Constructor Summary
HopcroftMinimizer()
           
 
Method Summary
static void main(java.lang.String[] args)
           
 DFA minimize(DFA a)
          Returns the minimal DFA equivalent to a computed by Hopcroft's algorithm.
 DFT minimize(DFT a)
          Returns the minimal DFT equivalent to a normalized DFT a computed by Hopcroft's algorithm.
 IDFA minimize(IDFA a)
           
 Partition stabilize(DFA a, Partition partition)
          This method computes the partition refining partition which is compatible whith the DFA a.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

verbose

public static boolean verbose
A boolean flag allowing to set a verbose mode. Useful for tutorial purpose and also for debugging. Not convenient when the automaton is too large.

Constructor Detail

HopcroftMinimizer

public HopcroftMinimizer()
Method Detail

minimize

public DFA minimize(DFA a)
             throws java.lang.Exception
Returns the minimal DFA equivalent to a computed by Hopcroft's algorithm.

Specified by:
minimize in interface Minimizer
Throws:
java.lang.Exception

minimize

public DFT minimize(DFT a)
             throws java.lang.Exception
Returns the minimal DFT equivalent to a normalized DFT a computed by Hopcroft's algorithm. The same as the above except for the initial partition which takes into account the output labels.

Specified by:
minimize in interface Minimizer
Throws:
java.lang.Exception

minimize

public IDFA minimize(IDFA a)
              throws java.lang.Exception
Specified by:
minimize in interface Minimizer
Throws:
java.lang.Exception

stabilize

public Partition stabilize(DFA a,
                           Partition partition)
This method computes the partition refining partition which is compatible whith the DFA a.


main

public static void main(java.lang.String[] args)
                 throws java.lang.Exception
Throws:
java.lang.Exception