Class NFT

java.lang.Object
  extended byNFA
      extended byNFT

public class NFT
extends NFA

This class implements nondeterministic finite-state transducers (NFT). The states are represented by integers and the transitions by an array of sets of ternary half-edges, i.e. triples (s, t, q) of an input word, an output word and a state (class HalfEdge). A set of half edges is represented by a TreeSet. The sets of initial and terminal states are represented by TreeSet objects. The alphabet is given as an object of the class Alpabet.


Constructor Summary
NFT(int n)
          Creates an NFT n with states.
NFT(int n, Alphabet a)
          Creates an NFT with n states on the alphabet a.
NFT(int n, int k)
          Creates an NFT with n states and k letters.
 
Method Summary
static NFT circularRightShift()
          The circular right shift.
 java.util.Set closure(HalfEdge p, boolean[] mark)
          Returns the list of binary half-edges of the form p followed by a path with input epsilon.
 java.util.Set closure(java.util.Set s)
          idem from the half edges of the set s
static NFT compose(NFT s, NFT t)
          Returns the composition of the NFT s and t, which are supposed to be literal.
static NFT epsilon()
          An NFT realizing \e \times a^*.
 java.util.LinkedList explore(java.util.LinkedList t, int p, DFT b)
          Implements the function Explore(t, s, b) which returns the list of sets of half edges realizing the determinization of the NFT.
static NFT fibonacci()
          The literal NFT realizing the Fibonacci morphism a->ab, b->a.
 int LmaxOutput()
          The maximal length of outputs in an NFT.
static java.lang.String longestCommonPrefix(java.util.Set s)
          Returns the longest common prefix of the half-edges forming the set s.
static void main(java.lang.String[] args)
           
 java.util.Set next(java.util.Set s, int c)
          Computes a set transition in an input literal NFT.
 void normalize(java.util.Set s)
          Erases the lCP of all strings in a set of binary half-edges.
 java.lang.String output(java.util.Set s)
          Returns the string w such that (w,t) is in the set s for some terminal state t.
static NFT saka1()
          A determinisable NFT.
static NFT saka2()
          A determinisable NFT.
static NFT saka3()
          A nondeterminisable NFT.
static NFT saka4()
          A nondeterminisable NFT.
 DFT toDFT()
          Returns the determinization of the NFA.
 boolean tooLong(java.util.Set l)
          Returns true if the label of a half-edge in the set l exceeds the bound 2 * LmaxOutput() * n * n.
 
Methods inherited from class NFA
count, explore, explore2, toDFA, toDFA2, toDFA3, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

NFT

public NFT(int n)
Creates an NFT n with states.


NFT

public NFT(int n,
           int k)
Creates an NFT with n states and k letters.


NFT

public NFT(int n,
           Alphabet a)
Creates an NFT with n states on the alphabet a.

Method Detail

circularRightShift

public static NFT circularRightShift()
The circular right shift. A 4 states NFA (deterministic, except for the two initial states.


fibonacci

public static NFT fibonacci()
The literal NFT realizing the Fibonacci morphism a->ab, b->a.


epsilon

public static NFT epsilon()
An NFT realizing \e \times a^*.


saka1

public static NFT saka1()
A determinisable NFT.


saka2

public static NFT saka2()
A determinisable NFT.


saka3

public static NFT saka3()
A nondeterminisable NFT.


saka4

public static NFT saka4()
A nondeterminisable NFT.


compose

public static NFT compose(NFT s,
                          NFT t)
Returns the composition of the NFT s and t, which are supposed to be literal. The states are pairs (p,q) of a state of t and a state of s coded by the integer p * t.nbStates + q.


closure

public java.util.Set closure(HalfEdge p,
                             boolean[] mark)
Returns the list of binary half-edges of the form p followed by a path with input epsilon.

Overrides:
closure in class NFA
Parameters:
p - a binary half edge
mark - a boolean array used to mark the visited states
Returns:
the set of binary half-edges obtained by following an epsilon input path after p

closure

public java.util.Set closure(java.util.Set s)
idem from the half edges of the set s

Overrides:
closure in class NFA

next

public java.util.Set next(java.util.Set s,
                          int c)
Computes a set transition in an input literal NFT. The transition uses an edge labeled c followed by a path with epsilon input.

Overrides:
next in class NFA
Parameters:
s - a set of binary half edges
c - a letter
Returns:
the list of half edges obtained

longestCommonPrefix

public static java.lang.String longestCommonPrefix(java.util.Set s)
Returns the longest common prefix of the half-edges forming the set s.

Parameters:
s - a set of binary half-edges
Returns:
the longest common prefix of the half-edges forming the set s.

normalize

public void normalize(java.util.Set s)
Erases the lCP of all strings in a set of binary half-edges.


explore

public java.util.LinkedList explore(java.util.LinkedList t,
                                    int p,
                                    DFT b)
                             throws java.lang.Exception
Implements the function Explore(t, s, b) which returns the list of sets of half edges realizing the determinization of the NFT. The third argument is the resulting DFT. The exploration starts at the element s of t with order p.

Parameters:
t - a linked list of sets of half-edges.
p - the order of the starting list.
b - the resulting DFT.
Returns:
the linked list of states of b.
Throws:
java.lang.Exception

output

public java.lang.String output(java.util.Set s)
                        throws java.lang.Exception
Returns the string w such that (w,t) is in the set s for some terminal state t. Throws an exception if there are several possible strings.

Throws:
java.lang.Exception

LmaxOutput

public int LmaxOutput()
The maximal length of outputs in an NFT.


tooLong

public boolean tooLong(java.util.Set l)
Returns true if the label of a half-edge in the set l exceeds the bound 2 * LmaxOutput() * n * n.


toDFT

public DFT toDFT()
Returns the determinization of the NFA.


main

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