Class NbisMinimizer

java.lang.Object
  NbisMinimizer

All Implemented Interfaces:

Minimizer

public class NbisMinimizer

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

NbisMinimizer()

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

NbisMinimizer

public NbisMinimizer()

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)