Class LinkedNFA

java.lang.Object
  LinkedNFA

public class LinkedNFA

extends java.lang.Object

Implementation of Thomson's algorithm to perform the operations of union, product and star on automata. The automata have the properties that there are at most two edges going out of a state, there is only one initial state, only one terminal state, no edge comes into the initial state, no edge goes out of the terminal state.

Constructor Summary

LinkedNFA()
Creates a one-state NFA recognizing epsilon.

LinkedNFA(char a)
Implements BuildAutomaton(a).

LinkedNFA(State i, State t)
Implements NewAutomaton(i,t).

Method Summary

static LinkedNFA	automataProduct(LinkedNFA a, LinkedNFA b) Implements the function AutomataProduct().
static LinkedNFA	automataUnion(LinkedNFA a, LinkedNFA b) Implements the function AutomataUnion().
static LinkedNFA	automatonStar(LinkedNFA a) Implements the function NFAStar().
static void	main(java.lang.String[] args)
NFA	toNFA(Alphabet alph) Converts a LinkedNFA into an NFA.
void	toNFA(NFA a, State p) The recursive call to run toNFA.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

LinkedNFA

public LinkedNFA()

Creates a one-state NFA recognizing epsilon.

LinkedNFA

public LinkedNFA(char a)

Implements BuildAutomaton(a). Creates a two-states NFA recognizing a

Parameters:

a - a character

LinkedNFA

public LinkedNFA(State i,
                 State t)

Implements NewAutomaton(i,t). Creates a NFA with i as initial state and t as terminal state.

Parameters:

i - initial state

t - terminal state

Method Detail

automataUnion

public static LinkedNFA automataUnion(LinkedNFA a,
                                      LinkedNFA b)

Implements the function AutomataUnion(). Runs in constant time.

Parameters:

a - a NFA

b - another NFA

Returns:

the NFA recognizing the union of the sets recognized by a and b.

automataProduct

public static LinkedNFA automataProduct(LinkedNFA a,
                                        LinkedNFA b)

Implements the function AutomataProduct(). Runs in constant time.

Parameters:

a - a NFA

b - another NFA

Returns:

the NFA recognizing the product of the sets recognized by a and b.

automatonStar

public static LinkedNFA automatonStar(LinkedNFA a)

Implements the function NFAStar(). Runs in constant time.

Parameters:

a - a NFA

Returns:

the NFA recognizing the star of the set recognized by a.

toString

public java.lang.String toString()

toNFA

public NFA toNFA(Alphabet alph)

Converts a LinkedNFA into an NFA.

Parameters:

alph - the input alphabet

Returns:

the equivalent NFA on the alphabet alpha

toNFA

public void toNFA(NFA a,
                  State p)

The recursive call to run toNFA.

main

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

Throws:

java.lang.Exception