Class INFA

java.lang.Object
  INFA

public class INFA

extends java.lang.Object

This class implements incomplete nondeterministic finite automata (without epsilon transitions). The edges going out of a state are implemented in a Queue (class PairIntQueue). The automaton itself is an array of Queues.

Field Summary

Alphabet	alphabet The alphabet.
PairIntQueue[]	edges The set of edges going out of a state.
java.util.Set	initial The set of initial states.
int	nbLetters
int	nbStates The number of states.
java.util.Set	terminal The set of terminal states.

Constructor Summary

INFA()

INFA(int n)

INFA(int n, Alphabet a)

Method Summary

void	addEdge(int p, char a, int q)
void	addEdge(int p, int a, int q)
void	addTerminal(int p)
static INFA	ex()
java.util.LinkedList	explore(java.util.LinkedList t, int p, IDFA b) Implements the function Explore(t, s, b) which returns the list of sets of half edges realizing the determinization of the NFA.
boolean	isTerminal(int p)
static void	main(java.lang.String[] args)
java.util.Set[]	next(java.util.Set s) Computes a set transition in an INFA.
IDFA	toIDFA(int Nmax) 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

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 set of initial states.

terminal

public java.util.Set terminal

The set of terminal states.

alphabet

public Alphabet alphabet

The alphabet.

Constructor Detail

INFA

public INFA()

INFA

public INFA(int n)

INFA

public INFA(int n,
            Alphabet a)

Method Detail

isTerminal

public boolean isTerminal(int p)

addTerminal

public void addTerminal(int p)

addEdge

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

addEdge

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

toString

public java.lang.String toString()

ex

public static INFA ex()

next

public java.util.Set[] next(java.util.Set s)

Computes a set transition in an INFA.

Parameters:

s - the original set of states

Returns:

the array of sets of states reachable from s under input c.

explore

public java.util.LinkedList explore(java.util.LinkedList t,
                                    int p,
                                    IDFA b)

Implements the function Explore(t, s, b) 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.

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

main

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