Class ICFA

java.lang.Object
  ICFA

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)