Class NFT

java.lang.Object
  NFA
      NFT

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)