Class DFT

java.lang.Object
  DFA
      DFT

public class DFT

extends DFA

This class implements sequential (or deterministic) finite-state transducers. These inherit from deterministic finite-state automata (DFA) adding an output function, an initial output (associated with the initial state) and a terminal output function. The terminal states are those with a nonempty output.

Constructor Summary

DFT(int n, Alphabet a)
creates a DFT with n states and alphabet a.

DFT(int n, int k)
creates a DFT with n states and k letters.

Method Summary

static DFT	compose(DFT a, DFT b) Returns the composition of the DFT a and b.
int[]	initClass()
Partition	initPartition()
static int[]	intersection(int[] table1, int[] table2) Returns the partition intersection of table1 and table2.
static int[]	intersection(int[] table, java.lang.String[] label) returns the partition intersection of table and label.
java.lang.String[]	lcp() Returns the vector of longest common prefixes of an DFT.
static java.lang.String	lcp(java.lang.String s, java.lang.String t) Returns the longest common prefix of the strings s and t.
static void	main(java.lang.String[] args)
static DFT	minimize(DFT a, Minimizer m) Minimizes the DFT using the method m.
void	normalize() Normalizes the DFT, pushing the output to the left.
java.lang.String	output(java.lang.String s) Returns the output corresponding to the input s.
DFT	quotientDFT(int[] c) Returns the quotient of the DFT by the partition c
DFT	quotientDFT(Partition p)
void	refine(java.lang.String[] m) Realizes the iteration m=Um+v with operations in the semiring (lcp,.,0,\e) where m is a vector of strings, U the matrix of outputs and v the vector of terminal outputs.
java.lang.String	star(int q, java.lang.String s) Returns the output from state q under input w (without regard to terminal states and a possible terminal output).
java.lang.String	toString()

Methods inherited from class DFA

minimize, minimize, next, quotient, quotient

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

DFT

public DFT(int n,
           int k)

creates a DFT with n states and k letters.

DFT

public DFT(int n,
           Alphabet a)

creates a DFT with n states and alphabet a.

Method Detail

star

public java.lang.String star(int q,
                             java.lang.String s)

Returns the output from state q under input w (without regard to terminal states and a possible terminal output).

output

public java.lang.String output(java.lang.String s)

Returns the output corresponding to the input s.

compose

public static DFT compose(DFT a,
                          DFT b)

Returns the composition of the DFT a and b. The method is a particular case of the composition of NFT. The corresponding transduction applies first a and then b. The states are pairs (q,p) of a state of b and a state of a coded by the integer q * a.nbStates + p.

toString

public java.lang.String toString()

Overrides:

toString in class DFA

lcp

public static java.lang.String lcp(java.lang.String s,
                                   java.lang.String t)

Returns the longest common prefix of the strings s and t.

Parameters:

s - a string

t - a string

Returns:

the longest common prefix of the strings s and t.

refine

public void refine(java.lang.String[] m)

Realizes the iteration m=Um+v with operations in the semiring (lcp,.,0,\e) where m is a vector of strings, U the matrix of outputs and v the vector of terminal outputs.

Parameters:

m - an array of strings or 0 (=null)

Returns:

Um+v

lcp

public java.lang.String[] lcp()

Returns the vector of longest common prefixes of an DFT. lcp[p] is the longest common prefix of the strings star(p,w)

Returns:

the array of longest common prefixes

normalize

public void normalize()

Normalizes the DFT, pushing the output to the left.

minimize

public static DFT minimize(DFT a,
                           Minimizer m)
                    throws java.lang.Exception

Minimizes the DFT using the method m.

Throws:

java.lang.Exception

initClass

public int[] initClass()

initPartition

public Partition initPartition()

intersection

public static int[] intersection(int[] table,
                                 java.lang.String[] label)

returns the partition intersection of table and label.

Parameters:

table - an array of integers

label - an array of String of the same size

Returns:

the array resulting of the partition intersection.

intersection

public static int[] intersection(int[] table1,
                                 int[] table2)

Returns the partition intersection of table1 and table2.

Parameters:

table1 - an array of integers

table2 - an array of integers of the same size

Returns:

the array resulting of the partition intersection.

quotientDFT

public DFT quotientDFT(int[] c)

Returns the quotient of the DFT by the partition c

Parameters:

c - a partition of the state set

Returns:

the new DFA

quotientDFT

public DFT quotientDFT(Partition p)

main

public static void main(java.lang.String[] args)