Class DFT

java.lang.Object
  extended byDFA
      extended byDFT

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)