Class NFA

java.lang.Object
  extended byNFA
Direct Known Subclasses:
InfoNFA, NFT

public class NFA
extends java.lang.Object

This class implements nondeterministic finite automata. The states are represented by integers and the transitions by sets of half-edges, i.e. of pairs (s, q) of a word and a state. The half-edges are objects of the class HalfEdge. A set of half-edges 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

NFA

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


NFA

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


NFA

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

Method Detail

toString

public java.lang.String toString()

closure

public java.util.Set closure(HalfEdge p,
                             boolean[] mark)
Returns the set of states which can be reached from p by an epsilon path. Implements a depth-first search of the graph of epsilon transitions. Uses a boolean array mark for the exploration.

Parameters:
p - a state (i.e. a unary half-edge)
mark - the array of marks
Returns:
the set of states obtained.

closure

public java.util.Set closure(java.util.Set s)
Implements the closure of the set of states s.


next

public java.util.Set next(java.util.Set s,
                          int c)
Computes a set transition in a literal NFA. The complexity is 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).

Parameters:
s - the original set of states
c - a letter
Returns:
the set of states reachable from s under input c.

count

public 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.

Parameters:
t - a linked list of sets of states (implemented as TreeSet).
p - the order of the starting set.
Returns:
the linked list of states of the determinized automaton.

explore

public 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. The third argument is the resulting DFA. The exploration starts at the element s of t with order p.

Parameters:
t - a linked list of sets of states (implemented as TreeSet).
p - the order of the starting set.
b - the resulting DFA.
Returns:
the linked list of states of b.

toDFA

public DFA toDFA()
Implements the determinization algorithm. The size of the 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)).


toDFA3

public DFA toDFA3()
Implements the determinization algorithm. The size of the 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)).


explore2

public 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.


toDFA2

public DFA toDFA2()
The same as toDFA but with an implementation of the set of states of the resulting DFA via a HashMap. The keys are the sets of half-edges (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.


main

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