regaut

Class NFA

java.lang.Object

regaut.NFA

All Implemented Interfaces:

java.lang.Cloneable

public class NFA
extends java.lang.Object
implements java.lang.Cloneable

Nondeterministic finite state automaton with transitions. [Martin, Th. 3.12]

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor and Description
NFA() Constructs an uninitialized NFA.

Method Summary

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

Set of State objects (Q).

transitions

public java.util.Map<StateSymbolPair,java.util.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

NFA

public NFA()

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

Method Detail

accepts

public boolean accepts(java.lang.String s)
                throws java.lang.IllegalArgumentException

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

Parameters:

s - a string

Returns:

true iff the string is accepted

Throws:

java.lang.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 NFA checkWellDefined()
                     throws AutomatonNotWellDefinedException

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

Returns:

this automaton

Throws:

AutomatonNotWellDefinedException - if this automaton is not well-defined

clone

public java.lang.Object clone()

Clones this automaton.

Overrides:

clone in class java.lang.Object

concat

public NFA concat(NFA f)
           throws java.lang.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. 3.25] The input automata are unmodified.

Throws:

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

delta

public java.util.Set<State> delta(State q,
                                  char c)
                           throws java.lang.IllegalArgumentException

Looks up transitions in transition function.

Returns:

(q,c)

Throws:

java.lang.IllegalArgumentException - if c is not in the alphabet

deltaStar

public java.util.Set<State> deltaStar(State q,
                                      java.lang.String s)
                               throws java.lang.IllegalArgumentException

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

Returns:

*(q,s)

Throws:

java.lang.IllegalArgumentException - if a symbol in s is not in the alphabet

determinize

public FA determinize()

Determinizes this automaton by constructing an equivalent FA. [Martin, Th. 3.18] The input automaton is unmodified. This implementation only constructs the reachable part of the subset state space. It first calls removeLambdas() to eliminate transitions.

getNumberOfStates

public int getNumberOfStates()

Returns number of states in this automaton.

kleene

public NFA kleene()

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

lambdaClosure

public java.util.Set<State> lambdaClosure(java.util.Set<State> set)

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

Parameters:

set - set of State objects

Returns:

set of State objects (the input set is unmodified)

makeEmptyLanguage

public static NFA makeEmptyLanguage(Alphabet a)

Constructs a new NFA that accepts the empty language. [Martin, Th. 3.25]

Parameters:

a - automaton alphabet

makeEmptyString

public static NFA makeEmptyString(Alphabet a)

Constructs a new NFA that accepts the language containing only the empty string.

Parameters:

a - automaton alphabet

makeSingleton

public static NFA makeSingleton(Alphabet a,
                                char c)

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

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 (and if necessary, making the initial state an accept state). [Martin, Th. 3.17] The input automaton is unmodified.

toDot

public java.lang.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 NFA union(NFA f)
          throws java.lang.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. 3.25] The input automata are unmodified.

Throws:

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