dRegAut
Class FA

java.lang.Object
  dRegAut.FA

All Implemented Interfaces:

Cloneable

public class FA
extends Object
implements Cloneable

Deterministic finite state automaton. [Martin, Def. 2.11]

Field Summary

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

Constructor Summary

FA()
Constructs an uninitialized FA.

FA(Alphabet a)
Constructs a new FA consisting of one reject state.

Method Summary

boolean	accepts(String s) Runs the given string on this automaton.
FA	checkWellDefined() Checks that this automaton is well-defined.
Object	clone() Clones this automaton.
FA	complement() Constructs a new automaton that accepts the complement of the language of this automaton.
State	delta(State q, char c) Looks up transition in transition function.
State	deltaStar(State q, String s) Performs transitions in extended transition function.
boolean	equals(Object obj) Checks whether the language of this automaton is equal to the language of the given automaton.
Set<State>	findReachableStates() Finds the set of states that are reachable from the initial state.
String	getAShortestExample() Returns a shortest string that is accepted by this automaton.
int	getNumberOfStates() Returns number of states in this automaton.
int	hashCode() Computes hash code for this object.
FA	intersection(FA f) Constructs a new automaton whose language is the intersection of the language of this automaton and the language of the given automaton.
boolean	isEmpty() Checks whether the language of this automaton is empty.
boolean	isFinite() Checks whether the language of this automaton is finite.
FA	minimize() Constructs a new minimal automaton with the same language as this automaton.
FA	minus(FA f) Constructs a new automaton whose language is equal to the language of this automaton minus the language of the given automaton.
FA	removeUnreachableStates() Constructs a new automaton with the same language as this automaton but without unreachable states.
void	setTransition(State q, char c, State p) Sets a transition in the transition function.
boolean	subsetOf(FA f) Checks whether the language of this automaton is a subset of the language of the given automaton.
String	toDot() Returns Graphviz Dot representation of this automaton.
NFA	toNFA() Converts this FA into an equivalent NFA.
RegExp	toRegExp() Converts this automaton into an equivalent RegExp regular expression.
FA	union(FA 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

finalize, getClass, 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.

states

public Set<State> states

Set of State objects (Q).

transitions

public Map<StateSymbolPair,State> transitions

Transition function (). This is a map from pairs of states and alphabet symbols to states (: Q Q).

Constructor Detail

FA

public FA()

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

FA

public FA(Alphabet a)

Constructs a new FA consisting of one reject state.

Parameters:

a - automaton alphabet

Method Detail

accepts

public boolean accepts(String s)
                throws IllegalArgumentException

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

Parameters:

s - a string

Returns:

true iff the string is accepted

Throws:

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

checkWellDefined

public FA checkWellDefined()
                    throws AutomatonNotWellDefinedException

Checks that this automaton is well-defined. In particular, this method checks that the transition function is total. This method should be invoked after each FA 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

complement

public FA complement()

Constructs a new automaton that accepts the complement of the language of this automaton. The input automaton is unmodified.

delta

public State delta(State q,
                   char c)
            throws IllegalArgumentException

Looks up transition in transition function.

Returns:

(q,c)

Throws:

IllegalArgumentException - if c is not in the alphabet

deltaStar

public State deltaStar(State q,
                       String s)
                throws IllegalArgumentException

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

Returns:

*(q,s)

Throws:

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

equals

public boolean equals(Object obj)

Checks whether the language of this automaton is equal to the language of the given automaton.

Overrides:

equals in class Object

findReachableStates

public Set<State> findReachableStates()

Finds the set of states that are reachable from the initial state. [Martin, Exercise 2.27(b)]

getAShortestExample

public String getAShortestExample()

Returns a shortest string that is accepted by this automaton.

Returns:

a (not necessarily unique) shortest example string, null if the language of this automaton is empty

getNumberOfStates

public int getNumberOfStates()

Returns number of states in this automaton.

hashCode

public int hashCode()

Computes hash code for this object. (When equals(Object) is implemented, hashCode must also be there.)

Overrides:

hashCode in class Object

intersection

public FA intersection(FA f)
                throws IllegalArgumentException

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

Throws:

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

isEmpty

public boolean isEmpty()

Checks whether the language of this automaton is empty. [Martin, Example 2.34]

isFinite

public boolean isFinite()

Checks whether the language of this automaton is finite. [Martin, Example 2.34]

minimize

public FA minimize()

Constructs a new minimal automaton with the same language as this automaton. [Martin, Sec. 2.6] The input automaton is unmodified. Note: this textbook algorithm is simple to understand but not very efficient compared to other existing algorithms.

minus

public FA minus(FA f)
         throws IllegalArgumentException

Constructs a new automaton whose language is equal to the language of this automaton minus the language of the given automaton. [Martin, Th. 2.15] The input automata are unmodified.

Throws:

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

removeUnreachableStates

public FA removeUnreachableStates()

Constructs a new automaton with the same language as this automaton but without unreachable states. The input automaton is unmodified.

setTransition

public void setTransition(State q,
                          char c,
                          State p)

Sets a transition in the transition function. (q,c)=p

subsetOf

public boolean subsetOf(FA f)

Checks whether the language of this automaton is a subset of the language of the given automaton. [Martin, Exercise 2.27(g)]

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'.)

toNFA

public NFA toNFA()

Converts this FA into an equivalent NFA. Note: this is trivial since an FA is just a special kind of NFA, except for the different representation.

toRegExp

public RegExp toRegExp()

Converts this automaton into an equivalent RegExp regular expression. [Martin, Th. 3.30]

union

public FA union(FA 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. 2.15] The input automata are unmodified.

Throws:

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

See Also:

NFA.union(dRegAut.NFA)