Class NFA

java.lang.Object
  NFA

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)