

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object NFA
This class implements nondeterministic finite automata.
The states are represented by integers and the transitions
by sets of halfedges, i.e. of pairs (s, q)
of a
word and a state. The halfedges are objects of the class
HalfEdge
.
A set of halfedges is represented as a Set
(actually a
TreeSet).
The set of initial and the set of terminal states are
also represented by a Set
.
The alphabet is given as an object of the class
Alpabet
.
Constructor Summary  
NFA(int n)
Creates an NFA with n states. 

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

NFA(int n,
int k)
Creates an NFA with n states
and k letters. 
Method Summary  
java.util.Set 
closure(HalfEdge p,
boolean[] mark)
Returns the set of states which can be reached from p
by an epsilon path. 
java.util.Set 
closure(java.util.Set s)
Implements the closure of the set of states s . 
java.util.LinkedList 
count(java.util.LinkedList t,
int p)
Returns the number of states of the result of the determinization algorithm without constructing the automaton. 
java.util.LinkedList 
explore(java.util.LinkedList t,
int p,
DFA b)
Implements the function Explore(t, s, b) of Section 1.3.3
which returns
the list of sets of half edges realizing the determinization
of the NFA. 
int 
explore2(java.util.HashMap t,
java.util.Set s,
int nn,
DFA b)
The same as explore but with an implementation of the
set of states of the resulting DFA via a HashMap . 
static void 
main(java.lang.String[] args)

java.util.Set 
next(java.util.Set s,
int c)
Computes a set transition in a literal NFA. 
DFA 
toDFA()
Implements the determinization algorithm. 
DFA 
toDFA2()
The same as toDFA but with an implementation of the
set of states of the resulting DFA via a HashMap .

DFA 
toDFA3()
Implements the determinization algorithm. 
java.lang.String 
toString()

Methods inherited from class java.lang.Object 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait 
Constructor Detail 
public NFA(int n)
n
states.
public NFA(int n, int k)
n
states
and k
letters.
public NFA(int n, Alphabet a)
n
states
on the alphabet a
.
Method Detail 
public java.lang.String toString()
public java.util.Set closure(HalfEdge p, boolean[] mark)
p
by an epsilon path. Implements a depthfirst search of the
graph of epsilon transitions.
Uses a boolean array mark
for the exploration.
p
 a state (i.e. a unary halfedge)mark
 the array of marks
public java.util.Set closure(java.util.Set s)
s
.
public java.util.Set next(java.util.Set s, int c)
O(n log(n))
for an NFA
with n
states. Indeed, the set s
has O(n)
elements
and each insertion costs time log(n)
using a TreeSet
to represent the sets s
and next(s, c)
.
s
 the original set of statesc
 a letter
public java.util.LinkedList count(java.util.LinkedList t, int p)
t
 a linked list of sets of states (implemented as TreeSet).p
 the order of the starting set.
public java.util.LinkedList explore(java.util.LinkedList t, int p, DFA b)
Explore(t, s, b)
of Section 1.3.3
which returns
the list of sets of half edges realizing the determinization
of the NFA. The third argument is the resulting DFA. The exploration
starts at the element s
of t
with order p
.
t
 a linked list of sets of states (implemented as TreeSet).p
 the order of the starting set.b
 the resulting DFA.
b
.public DFA toDFA()
DFA
created is given by the static constant Nmax
.
Implements the function NFAtoDFA
of Section 1.3.3.
The set of states of the resulting DFA
is implemented
as a LinkedList
. The complexity is O(n m^2)
on an NFA
of size n
resulting in a DFA
of size m
.. Indeed, each call to
explore
needs a search into the list of sets of states
(which contains O(m)
sets of size O(n)
).
public DFA toDFA3()
DFA
created is first computed using the method count
.
Implements the function NFAtoDFA
of Section 1.3.3.
The set of states of the resulting DFA
is implemented
as a LinkedList
. The complexity is O(n m^2)
on an NFA
of size n
resulting in a DFA
of size m
.. Indeed, each call to
explore
needs a search into the list of sets of states
(which contains O(m)
sets of size O(n)
).
public int explore2(java.util.HashMap t, java.util.Set s, int nn, DFA b)
explore
but with an implementation of the
set of states of the resulting DFA
via a HashMap
.
public DFA toDFA2()
toDFA
but with an implementation of the
set of states of the resulting DFA
via a HashMap
.
The keys are the sets of halfedges (with the method hashCode
overridden in the class HalfEdge
) and the value is the name
of the state. Assuming constant time performance for the functions
get
andput
, the complexity is O(m n log(n))
on an NFA
of size n
resulting in a DFA
with m
states.
public static void main(java.lang.String[] args)


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 