dk.brics.automaton

Class Automaton

public class Automaton extends Object implements Serializable, Cloneable

Finite-state automaton with regular expression operations.

Class invariants:

If the states or transitions are manipulated manually, the restoreInvariant and Automaton methods should be used afterwards to restore representation invariants that are assumed by the built-in automata operations.

Author: Anders Møller <amoeller@cs.au.dk>

Field Summary
static intMINIMIZE_BRZOZOWSKI
Minimize using Brzozowski's O(2n) algorithm.
static intMINIMIZE_HOPCROFT
Minimize using Hopcroft's O(n log n) algorithm.
static intMINIMIZE_HUFFMAN
Minimize using Huffman's O(n2) algorithm.
Constructor Summary
Automaton()
Constructs a new automaton that accepts the empty language.
Method Summary
voidaddEpsilons(Collection<StatePair> pairs)
Automatoncomplement()
Automatoncompress(String set, char c)
Automatonconcatenate(Automaton a)
static Automatonconcatenate(List<Automaton> l)
voiddeterminize()
voidexpandSingleton()
Expands singleton representation to normal representation.
Set<State>getAcceptStates()
Returns the set of reachable accept states.
StringgetCommonPrefix()
Set<String>getFiniteStrings()
Set<String>getFiniteStrings(int limit)
ObjectgetInfo()
Returns extra information associated with this automaton.
StategetInitialState()
Gets initial state.
Set<State>getLiveStates()
Returns the set of live states.
intgetNumberOfStates()
Returns the number of states in this automaton.
intgetNumberOfTransitions()
Returns the number of transitions in this automaton.
StringgetShortestExample(boolean accepted)
StringgetSingleton()
Returns the singleton string for this automaton.
Set<State>getStates()
Returns the set of states that are reachable from the initial state.
Set<String>getStrings(int length)
static AutomatonhexCases(Automaton a)
See hexCases.
Automatonhomomorph(char[] source, char[] dest)
Automatonintersection(Automaton a)
booleanisDeterministic()
Returns deterministic flag for this automaton.
booleanisEmpty()
See isEmpty.
booleanisEmptyString()
booleanisFinite()
See isFinite.
booleanisTotal()
See isTotal.
static Automatonload(URL url)
Retrieves a serialized Automaton located by a URL.
static Automatonload(InputStream stream)
Retrieves a serialized Automaton from a stream.
static AutomatonmakeAnyChar()
static AutomatonmakeAnyString()
static AutomatonmakeChar(char c)
static AutomatonmakeCharRange(char min, char max)
static AutomatonmakeCharSet(String set)
static AutomatonmakeDecimalValue(String value)
static AutomatonmakeEmpty()
See makeEmpty.
static AutomatonmakeEmptyString()
static AutomatonmakeFractionDigits(int i)
static AutomatonmakeIntegerValue(String value)
static AutomatonmakeInterval(int min, int max, int digits)
static AutomatonmakeMaxInteger(String n)
static AutomatonmakeMinInteger(String n)
static AutomatonmakeString(String s)
static AutomatonmakeStringMatcher(String s)
static AutomatonmakeStringUnion(CharSequence... strings)
static AutomatonmakeTotalDigits(int i)
voidminimize()
See minimize.
static Automatonminimize(Automaton a)
See minimize.
Automatonminus(Automaton a)
Automatonoptional()
See optional.
Automatonoverlap(Automaton a)
voidprefixClose()
AutomatonprojectChars(Set<Character> chars)
voidreduce()
Reduces this automaton.
voidremoveDeadTransitions()
Removes transitions to dead states and calls reduce and clearHashCode.
Automatonrepeat()
See repeat.
Automatonrepeat(int min)
Automatonrepeat(int min, int max)
static AutomatonreplaceWhitespace(Automaton a)
voidrestoreInvariant()
Restores representation invariant.
booleanrun(String s)
static booleansetAllowMutate(boolean flag)
Sets or resets allow mutate flag.
voidsetDeterministic(boolean deterministic)
Sets deterministic flag for this automaton.
voidsetInfo(Object info)
Associates extra information with this automaton.
voidsetInitialState(State s)
Sets initial state.
static voidsetMinimization(int algorithm)
Selects minimization algorithm (default: MINIMIZE_HOPCROFT).
static voidsetMinimizeAlways(boolean flag)
Sets or resets minimize always flag.
Automatonshuffle(Automaton a)
static StringshuffleSubsetOf(Collection<Automaton> ca, Automaton a, Character suspend_shuffle, Character resume_shuffle)
AutomatonsingleChars()
voidstore(OutputStream stream)
Writes this Automaton to the given stream.
booleansubsetOf(Automaton a)
Automatonsubst(Map<Character,Set<Character>> map)
Automatonsubst(char c, String s)
StringtoDot()
Returns Graphviz Dot representation of this automaton.
Automatontrim(String set, char c)
Automatonunion(Automaton a)
static Automatonunion(Collection<Automaton> l)
See union.

Field Detail

MINIMIZE_BRZOZOWSKI

public static final int MINIMIZE_BRZOZOWSKI
Minimize using Brzozowski's O(2n) algorithm. This algorithm uses the reverse-determinize-reverse-determinize trick, which has a bad worst-case behavior but often works very well in practice (even better than Hopcroft's!).

See Also: Automaton

MINIMIZE_HOPCROFT

public static final int MINIMIZE_HOPCROFT
Minimize using Hopcroft's O(n log n) algorithm. This is regarded as one of the most generally efficient algorithms that exist.

See Also: Automaton

MINIMIZE_HUFFMAN

public static final int MINIMIZE_HUFFMAN
Minimize using Huffman's O(n2) algorithm. This is the standard text-book algorithm.

See Also: Automaton

Constructor Detail

Automaton

public Automaton()
Constructs a new automaton that accepts the empty language. Using this constructor, automata can be constructed manually from State and Transition objects.

See Also: setInitialState State Transition

Method Detail

addEpsilons

public void addEpsilons(Collection<StatePair> pairs)
See BasicOperations.

complement

public Automaton complement()
See complement.

compress

public Automaton compress(String set, char c)
See SpecialOperations.

concatenate

public Automaton concatenate(Automaton a)
See BasicOperations.

concatenate

public static Automaton concatenate(List<Automaton> l)
See concatenate.

determinize

public void determinize()
See determinize.

expandSingleton

public void expandSingleton()
Expands singleton representation to normal representation. Does nothing if not in singleton representation.

getAcceptStates

public Set<State> getAcceptStates()
Returns the set of reachable accept states.

Returns: set of State objects

getCommonPrefix

public String getCommonPrefix()
See getCommonPrefix.

getFiniteStrings

public Set<String> getFiniteStrings()
See getFiniteStrings.

getFiniteStrings

public Set<String> getFiniteStrings(int limit)
See SpecialOperations.

getInfo

public Object getInfo()
Returns extra information associated with this automaton.

Returns: extra information

See Also: setInfo

getInitialState

public State getInitialState()
Gets initial state.

Returns: state

getLiveStates

public Set<State> getLiveStates()
Returns the set of live states. A state is "live" if an accept state is reachable from it.

Returns: set of State objects

getNumberOfStates

public int getNumberOfStates()
Returns the number of states in this automaton.

getNumberOfTransitions

public int getNumberOfTransitions()
Returns the number of transitions in this automaton. This number is counted as the total number of edges, where one edge may be a character interval.

getShortestExample

public String getShortestExample(boolean accepted)
See BasicOperations.

getSingleton

public String getSingleton()
Returns the singleton string for this automaton. An automaton that accepts exactly one string may be represented in singleton mode. In that case, this method may be used to obtain the string.

Returns: string, null if this automaton is not in singleton mode.

getStates

public Set<State> getStates()
Returns the set of states that are reachable from the initial state.

Returns: set of State objects

getStrings

public Set<String> getStrings(int length)
See SpecialOperations.

hexCases

public static Automaton hexCases(Automaton a)
See hexCases.

homomorph

public Automaton homomorph(char[] source, char[] dest)
See (Automaton, char[], char[]).

intersection

public Automaton intersection(Automaton a)
See BasicOperations.

isDeterministic

public boolean isDeterministic()
Returns deterministic flag for this automaton.

Returns: true if the automaton is definitely deterministic, false if the automaton may be nondeterministic

isEmpty

public boolean isEmpty()
See isEmpty.

isEmptyString

public boolean isEmptyString()
See isEmptyString.

isFinite

public boolean isFinite()
See isFinite.

isTotal

public boolean isTotal()
See isTotal.

load

public static Automaton load(URL url)
Retrieves a serialized Automaton located by a URL.

Parameters: url URL of serialized automaton

Throws: IOException if input/output related exception occurs OptionalDataException if the data is not a serialized object InvalidClassException if the class serial number does not match ClassCastException if the data is not a serialized Automaton ClassNotFoundException if the class of the serialized object cannot be found

load

public static Automaton load(InputStream stream)
Retrieves a serialized Automaton from a stream.

Parameters: stream input stream with serialized automaton

Throws: IOException if input/output related exception occurs OptionalDataException if the data is not a serialized object InvalidClassException if the class serial number does not match ClassCastException if the data is not a serialized Automaton ClassNotFoundException if the class of the serialized object cannot be found

makeAnyChar

public static Automaton makeAnyChar()
See makeAnyChar.

makeAnyString

public static Automaton makeAnyString()
See makeAnyString.

makeChar

public static Automaton makeChar(char c)
See BasicAutomata.

makeCharRange

public static Automaton makeCharRange(char min, char max)
See BasicAutomata.

makeCharSet

public static Automaton makeCharSet(String set)
See makeCharSet.

makeDecimalValue

public static Automaton makeDecimalValue(String value)
See makeDecimalValue.

makeEmpty

public static Automaton makeEmpty()
See makeEmpty.

makeEmptyString

public static Automaton makeEmptyString()
See makeEmptyString.

makeFractionDigits

public static Automaton makeFractionDigits(int i)
See BasicAutomata.

makeIntegerValue

public static Automaton makeIntegerValue(String value)
See makeIntegerValue.

makeInterval

public static Automaton makeInterval(int min, int max, int digits)
See BasicAutomata.

makeMaxInteger

public static Automaton makeMaxInteger(String n)
See makeMaxInteger.

makeMinInteger

public static Automaton makeMinInteger(String n)
See makeMinInteger.

makeString

public static Automaton makeString(String s)
See makeString.

makeStringMatcher

public static Automaton makeStringMatcher(String s)
See makeStringMatcher.

makeStringUnion

public static Automaton makeStringUnion(CharSequence... strings)
See BasicAutomata.

makeTotalDigits

public static Automaton makeTotalDigits(int i)
See BasicAutomata.

minimize

public void minimize()
See minimize.

minimize

public static Automaton minimize(Automaton a)
See minimize. Returns the automaton being given as argument.

minus

public Automaton minus(Automaton a)
See BasicOperations.

optional

public Automaton optional()
See optional.

overlap

public Automaton overlap(Automaton a)
See SpecialOperations.

prefixClose

public void prefixClose()
See prefixClose.

projectChars

public Automaton projectChars(Set<Character> chars)
See SpecialOperations.

reduce

public void reduce()
Reduces this automaton. An automaton is "reduced" by combining overlapping and adjacent edge intervals with same destination.

removeDeadTransitions

public void removeDeadTransitions()
Removes transitions to dead states and calls reduce and clearHashCode. (A state is "dead" if no accept state is reachable from it.)

repeat

public Automaton repeat()
See repeat.

repeat

public Automaton repeat(int min)
See BasicOperations.

repeat

public Automaton repeat(int min, int max)
See BasicOperations.

replaceWhitespace

public static Automaton replaceWhitespace(Automaton a)
See replaceWhitespace.

restoreInvariant

public void restoreInvariant()
Restores representation invariant. This method must be invoked before any built-in automata operation is performed if automaton states or transitions are manipulated manually.

See Also: Automaton

run

public boolean run(String s)
See BasicOperations.

setAllowMutate

public static boolean setAllowMutate(boolean flag)
Sets or resets allow mutate flag. If this flag is set, then all automata operations may modify automata given as input; otherwise, operations will always leave input automata languages unmodified. By default, the flag is not set.

Parameters: flag if true, the flag is set

Returns: previous value of the flag

setDeterministic

public void setDeterministic(boolean deterministic)
Sets deterministic flag for this automaton. This method should (only) be used if automata are constructed manually.

Parameters: deterministic true if the automaton is definitely deterministic, false if the automaton may be nondeterministic

setInfo

public void setInfo(Object info)
Associates extra information with this automaton.

Parameters: info extra information

setInitialState

public void setInitialState(State s)
Sets initial state.

Parameters: s state

setMinimization

public static void setMinimization(int algorithm)
Selects minimization algorithm (default: MINIMIZE_HOPCROFT).

Parameters: algorithm minimization algorithm

setMinimizeAlways

public static void setMinimizeAlways(boolean flag)
Sets or resets minimize always flag. If this flag is set, then minimize will automatically be invoked after all operations that otherwise may produce non-minimal automata. By default, the flag is not set.

Parameters: flag if true, the flag is set

shuffle

public Automaton shuffle(Automaton a)
See ShuffleOperations.

shuffleSubsetOf

public static String shuffleSubsetOf(Collection<Automaton> ca, Automaton a, Character suspend_shuffle, Character resume_shuffle)
See ShuffleOperations.

singleChars

public Automaton singleChars()
See singleChars.

store

public void store(OutputStream stream)
Writes this Automaton to the given stream.

Parameters: stream output stream for serialized automaton

Throws: IOException if input/output related exception occurs

subsetOf

public boolean subsetOf(Automaton a)
See BasicOperations.

subst

public Automaton subst(Map<Character,Set<Character>> map)
See SpecialOperations.

subst

public Automaton subst(char c, String s)
See SpecialOperations.

toDot

public String toDot()
Returns Graphviz Dot representation of this automaton.

trim

public Automaton trim(String set, char c)
See SpecialOperations.

union

public Automaton union(Automaton a)
See BasicOperations.

union

public static Automaton union(Collection<Automaton> l)
See union.
Copyright © 2001-2010 Anders Møller.