Class HopcroftMinimizer

java.lang.Object
  HopcroftMinimizer

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