Class ICFA

java.lang.Object
  extended byICFA

public class ICFA
extends java.lang.Object

This class implements incomplete codeterministic finite automata (ICFA). It is used mainly as a companion to the class IDFA. The method reverse applied to an IDFA produces an ICFA and conversely.


Field Summary
 Alphabet alphabet
          The alphabet.
 PairIntQueue[] edges
          The set of edges going out of a state.
 java.util.Set initial
          The initial set of states.
 int nbLetters
           
 int nbStates
          The number of states.
 int terminal
          The terminal state.
 
Constructor Summary
ICFA()
           
ICFA(int n)
           
ICFA(int n, Alphabet a)
           
 
Method Summary
 void addEdge(int p, char a, int q)
           
 void addEdge(int p, int a, int q)
           
 void addEdgeFast(int p, int a, int q)
           
static ICFA ex()
           
 java.util.LinkedList explore(java.util.LinkedList t, int p, IDFA 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, IDFA b)
          The same as explore but with an implementation of the set of states of the resulting DFA via a HashMap.
 java.util.LinkedList exploreBis(java.util.LinkedList t, java.util.Set s, int p, IDFA b)
          The same as explore but with a transmission of the index of the set s in the list t.
static void main(java.lang.String[] args)
           
 java.util.Set[] next(java.util.Set s)
          Computes a set transition in an ICFA as an array of sets indexed by the letters.
 IDFA reverse()
          Computes the deterministic automaton (IDFA) obtained by reversing the edges of a codeterministic automaton (ICFA).
 IDFA toIDFA(int Nmax)
          Implements the determinization algorithm.
 IDFA toIDFA2(int Nmax)
          The same as toIDFA but with an implementation of the set of states of the resulting IDFA via a HashMap.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

nbStates

public int nbStates
The number of states.


nbLetters

public int nbLetters

edges

public PairIntQueue[] edges
The set of edges going out of a state.


initial

public java.util.Set initial
The initial set of states.


terminal

public int terminal
The terminal state.


alphabet

public Alphabet alphabet
The alphabet.

Constructor Detail

ICFA

public ICFA()

ICFA

public ICFA(int n)

ICFA

public ICFA(int n,
            Alphabet a)
Method Detail

addEdge

public void addEdge(int p,
                    char a,
                    int q)

addEdge

public void addEdge(int p,
                    int a,
                    int q)

addEdgeFast

public void addEdgeFast(int p,
                        int a,
                        int q)

toString

public java.lang.String toString()

ex

public static ICFA ex()

next

public java.util.Set[] next(java.util.Set s)
Computes a set transition in an ICFA as an array of sets indexed by the letters. The complexity is O(e log(n)) for an NFA with e edges and 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
Returns:
the array of sets of states reachable from s under each input.

explore

public java.util.LinkedList explore(java.util.LinkedList t,
                                    int p,
                                    IDFA 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.

exploreBis

public java.util.LinkedList exploreBis(java.util.LinkedList t,
                                       java.util.Set s,
                                       int p,
                                       IDFA b)
The same as explore but with a transmission of the index of the set s in the list t.


explore2

public int explore2(java.util.HashMap t,
                    java.util.Set s,
                    int nn,
                    IDFA b)
The same as explore but with an implementation of the set of states of the resulting DFA via a HashMap.


toIDFA2

public IDFA toIDFA2(int Nmax)
The same as toIDFA but with an implementation of the set of states of the resulting IDFA 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 IDFA with m states.


reverse

public IDFA reverse()
Computes the deterministic automaton (IDFA) obtained by reversing the edges of a codeterministic automaton (ICFA). Complexity O(e) on an ICFA with e edges.


toIDFA

public IDFA toIDFA(int Nmax)
Implements the determinization algorithm. The sets of states created are represented by an object of the class TreeSet. The set of subsets created is stored as a list using the class LinkedList . Implements the function NFAtoDFA of Section 1.3.3.


main

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