|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object NFA NFT
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 |
public NFT(int n)
n
with states.
public NFT(int n, int k)
n
states
and k
letters.
public NFT(int n, Alphabet a)
n
states
on the alphabet a
.
Method Detail |
public static NFT circularRightShift()
public static NFT fibonacci()
a->ab, b->a
.
public static NFT epsilon()
\e \times a^*
.
public static NFT saka1()
public static NFT saka2()
public static NFT saka3()
public static NFT saka4()
public static NFT compose(NFT s, NFT t)
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
.
public java.util.Set closure(HalfEdge p, boolean[] mark)
p
followed by a path with input epsilon.
closure
in class NFA
p
- a binary half edgemark
- a boolean array used to mark the visited states
p
public java.util.Set closure(java.util.Set s)
s
closure
in class NFA
public java.util.Set next(java.util.Set s, int c)
c
followed by a path with epsilon input.
next
in class NFA
s
- a set of binary half edgesc
- a letter
public static java.lang.String longestCommonPrefix(java.util.Set s)
s
.
s
- a set of binary half-edges
s
.public void normalize(java.util.Set s)
public java.util.LinkedList explore(java.util.LinkedList t, int p, DFT b) throws java.lang.Exception
s
of
t
with order p
.
t
- a linked list of sets of half-edges.p
- the order of the starting list.b
- the resulting DFT.
b
.
java.lang.Exception
public java.lang.String output(java.util.Set s) throws java.lang.Exception
w
such that (w,t)
is in the set s
for some terminal state t
.
Throws an exception if there are several possible strings.
java.lang.Exception
public int LmaxOutput()
public boolean tooLong(java.util.Set l)
l
exceeds the bound 2 * LmaxOutput() * n * n
.
public DFT toDFT()
public static void main(java.lang.String[] args)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |