dRegAut
Class NFALambda

java.lang.Object
  dRegAut.NFALambda

All Implemented Interfaces:

Cloneable

public class NFALambda
extends Object
implements Cloneable

Nondeterministic finite state automaton with transitions.

Field Summary

Set<State>	accept Accept states (A).
Alphabet	alphabet The automaton alphabet ().
State	initial Initial state (q0).
static char	LAMBDA Our representation of .
Set<State>	states Set of State objects (Q).
Map<StateSymbolPair,Set<State>>	transitions Transition function ().

Constructor Summary

NFALambda()
Constructs an uninitialized NFALambda.

Method Summary

boolean	accepts(String s) Runs the given string on this automaton.
void	addLambda(State p, State q) Adds a transition.
NFALambda	checkWellDefined() Checks that this automaton is well-defined.
Object	clone() Clones this automaton.
NFALambda	concat(NFALambda f) Constructs a new automaton whose language is the concatenation of the language of this automaton and the language of the given automaton.
Set<State>	delta(State q, char c) Looks up transitions in transition function.
Set<State>	deltaStar(State q, String s) Performs transitions in extended transition function.
int	getNumberOfStates() Returns number of states in this automaton.
NFALambda	kleene() Constructs a new automaton whose language is the Kleene star of the language of this automaton.
Set<State>	lambdaClosure(Set<State> set) Computes the -closure of the given state set.
static NFALambda	makeEmptyLanguage(Alphabet a) Constructs a new NFALambda that accepts the empty language.
static NFALambda	makeEmptyString(Alphabet a) Constructs a new NFALambda that accepts the language containing only the empty string.
static NFALambda	makeSingleton(Alphabet a, char c) Constructs a new NFALambda that accepts the language containing only the given singleton string.
NFA	removeLambdas() Constructs an equivalent NFA by reducing all transitions to other transitions.
String	toDot() Returns Graphviz Dot representation of this automaton.
NFALambda	union(NFALambda f) Constructs a new automaton whose language is the union of the language of this automaton and the language of the given automaton.

Methods inherited from class java.lang.Object

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

Field Detail

accept

public Set<State> accept

Accept states (A). Subset of states.

alphabet

public Alphabet alphabet

The automaton alphabet ().

initial

public State initial

Initial state (q₀). Member of states.

LAMBDA

public static final char LAMBDA

Our representation of .

See Also:

Constant Field Values

states

public Set<State> states

Set of State objects (Q).

transitions

public Map<StateSymbolPair,Set<State>> transitions

Transition function (). This is a map from pairs of states and alphabet symbols to sets of states (: Q({}) 2^Q). We represent by LAMBDA.

Constructor Detail

NFALambda

public NFALambda()

Constructs an uninitialized NFALambda. states and accept are set to empty sets, transitions is set to an empty map.

Method Detail

accepts

public boolean accepts(String s)
                throws IllegalArgumentException

Runs the given string on this automaton. [Martin, Def. 4.5b]

Parameters:

s - a string

Returns:

true iff the string is accepted

Throws:

IllegalArgumentException - if a symbol in s is not in the alphabet

addLambda

public void addLambda(State p,
                      State q)

Adds a transition.

Parameters:

p - from state

q - to state

checkWellDefined

public NFALambda checkWellDefined()
                           throws AutomatonNotWellDefinedException

Checks that this automaton is well-defined. This method should be invoked after each NFALambda operation during testing.

Returns:

this automaton

Throws:

AutomatonNotWellDefinedException - if this automaton is not well-defined

clone

public Object clone()

Clones this automaton.

Overrides:

clone in class Object

concat

public NFALambda concat(NFALambda f)
                 throws IllegalArgumentException

Constructs a new automaton whose language is the concatenation of the language of this automaton and the language of the given automaton. [Martin, Th. 4.4] The input automata are unmodified.

Throws:

IllegalArgumentException - if the alphabets of f and this automaton are not the same

delta

public Set<State> delta(State q,
                        char c)
                 throws IllegalArgumentException

Looks up transitions in transition function.

Returns:

(q,c), the result is never null and it should never be modified by the caller

Throws:

IllegalArgumentException - if c is not in the alphabet

deltaStar

public Set<State> deltaStar(State q,
                            String s)
                     throws IllegalArgumentException

Performs transitions in extended transition function. [Martin, Def. 4.5]

Returns:

*(q,s) (the result is never null)

Throws:

IllegalArgumentException - if a symbol in s is not in the alphabet

getNumberOfStates

public int getNumberOfStates()

Returns number of states in this automaton.

kleene

public NFALambda kleene()

Constructs a new automaton whose language is the Kleene star of the language of this automaton. [Martin, Th. 4.4] The input automaton is unmodified.

lambdaClosure

public Set<State> lambdaClosure(Set<State> set)

Computes the -closure of the given state set. [Martin, Def. 4.6]

Parameters:

set - set of State objects

Returns:

set of State objects (the input set is unmodified)

makeEmptyLanguage

public static NFALambda makeEmptyLanguage(Alphabet a)

Constructs a new NFALambda that accepts the empty language. [Martin, Th. 4.4]

Parameters:

a - automaton alphabet

makeEmptyString

public static NFALambda makeEmptyString(Alphabet a)

Constructs a new NFALambda that accepts the language containing only the empty string. [Martin, Th. 4.4]

Parameters:

a - automaton alphabet

makeSingleton

public static NFALambda makeSingleton(Alphabet a,
                                      char c)

Constructs a new NFALambda that accepts the language containing only the given singleton string. [Martin, Th. 4.4]

Parameters:

a - automaton alphabet

c - the symbol in the singleton string

removeLambdas

public NFA removeLambdas()

Constructs an equivalent NFA by reducing all transitions to other transitions. [Martin, Th. 4.2] The input automaton is unmodified.

toDot

public String toDot()

Returns Graphviz Dot representation of this automaton. (To convert a dot file to postscript, run 'dot -Tps -o file.ps file.dot'.) Lambdas are written as '%'.

union

public NFALambda union(NFALambda f)
                throws IllegalArgumentException

Constructs a new automaton whose language is the union of the language of this automaton and the language of the given automaton. [Martin, Th. 4.4] The input automata are unmodified.

Throws:

IllegalArgumentException - if the alphabets of f and this automaton are not the same