Class NMinimizer

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

public class NMinimizer
extends java.lang.Object
implements Minimizer

This class implements a naive version of the Moore minimization algorithm in O(n^3).


Field Summary
static boolean verbose
           
 
Constructor Summary
NMinimizer()
           
 
Method Summary
 boolean equiv(DFA a, int p, int q, int[] c)
          Tests whether two states p,q are equivalent in the sense that p=q mod c and p.a=q.a mod c for every letter a .
 boolean equiv(IDFA a, int p, int q, int[] c)
           
 DFA minimize(DFA a)
          Returns the minimal automaton of a.
 DFT minimize(DFT a)
          Returns the minimal DFT of a.
 IDFA minimize(IDFA a)
           
 Partition partition(DFA a, Partition p)
          Computes the Nerode partition from the initial partition p.
 int[] partition(IDFA a, int[] p)
           
 Partition partition(IDFA a, Partition p)
           
 Partition refine(DFA a, Partition part)
          Refines the partition c.
 int[] refine(IDFA a, int[] c)
           
 Partition refine(IDFA a, Partition c)
           
 
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
Constructor Detail

NMinimizer

public NMinimizer()
Method Detail

minimize

public DFA minimize(DFA a)
             throws java.lang.Exception
Returns the minimal automaton of a.

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

minimize

public DFT minimize(DFT a)
             throws java.lang.Exception
Returns the minimal DFT of a.

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

partition

public Partition partition(DFA a,
                           Partition p)
Computes the Nerode partition from the initial partition p.

Parameters:
a - a DFA
p - the initial partition
Returns:
the Nerode partition

refine

public Partition refine(DFA a,
                        Partition part)
Refines the partition c.

Parameters:
a - a complete DFA
part - a partition of the state set
Returns:
the refined partition

equiv

public boolean equiv(DFA a,
                     int p,
                     int q,
                     int[] c)
Tests whether two states p,q are equivalent in the sense that p=q mod c and p.a=q.a mod c for every letter a .

Parameters:
a - a complete DFA
p - a state
q - a state
Returns:
true if p=q mod c and p.u=q.u mod c for every letter u

partition

public Partition partition(IDFA a,
                           Partition p)

partition

public int[] partition(IDFA a,
                       int[] p)

refine

public int[] refine(IDFA a,
                    int[] c)

refine

public Partition refine(IDFA a,
                        Partition c)

equiv

public boolean equiv(IDFA a,
                     int p,
                     int q,
                     int[] c)