dk.brics.automaton
Class Automaton

java.lang.Object
  extended by dk.brics.automaton.Automaton
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable

public class Automaton
extends java.lang.Object
implements java.io.Serializable, java.lang.Cloneable

Finite-state automaton with regular expression operations.

Class invariants:

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

Author:
Anders Møller <amoeller@brics.dk>
See Also:
Serialized Form

Field Summary
static int MINIMIZE_BRZOZOWSKI
          Minimize using Brzozowski's O(2n) algorithm.
static int MINIMIZE_HOPCROFT
          Minimize using Hopcroft's O(n log n) algorithm.
static int MINIMIZE_HUFFMAN
          Minimize using Huffman's O(n2) algorithm.
 
Constructor Summary
Automaton()
          Constructs a new automaton that accepts the empty language.
 
Method Summary
 void addEpsilons(java.util.Collection<StatePair> pairs)
          See BasicOperations.addEpsilons(Automaton, Collection).
 Automaton clone()
          Returns a clone of this automaton.
 Automaton complement()
          See BasicOperations.complement(Automaton).
 Automaton compress(java.lang.String set, char c)
          See SpecialOperations.compress(Automaton, String, char).
 Automaton concatenate(Automaton a)
          See BasicOperations.concatenate(Automaton, Automaton).
static Automaton concatenate(java.util.List<Automaton> l)
          See BasicOperations.concatenate(List).
 void determinize()
          See BasicOperations.determinize(Automaton).
 boolean equals(java.lang.Object obj)
          Returns true if the language of this automaton is equal to the language of the given automaton.
 void expandSingleton()
          Expands singleton representation to normal representation.
 java.util.Set<State> getAcceptStates()
          Returns the set of reachable accept states.
 java.lang.String getCommonPrefix()
          See SpecialOperations.getCommonPrefix(Automaton).
 java.util.Set<java.lang.String> getFiniteStrings()
          See SpecialOperations.getFiniteStrings(Automaton).
 java.util.Set<java.lang.String> getFiniteStrings(int limit)
          See SpecialOperations.getFiniteStrings(Automaton, int).
 java.lang.Object getInfo()
          Returns extra information associated with this automaton.
 State getInitialState()
          Gets initial state.
 java.util.Set<State> getLiveStates()
          Returns the set of live states.
 int getNumberOfStates()
          Returns the number of states in this automaton.
 int getNumberOfTransitions()
          Returns the number of transitions in this automaton.
 java.lang.String getShortestExample(boolean accepted)
          See BasicOperations.getShortestExample(Automaton, boolean).
 java.lang.String getSingleton()
          Returns the singleton string for this automaton.
 java.util.Set<State> getStates()
          Returns the set of states that are reachable from the initial state.
 java.util.Set<java.lang.String> getStrings(int length)
          See SpecialOperations.getStrings(Automaton, int).
 int hashCode()
          Returns hash code for this automaton.
static Automaton hexCases(Automaton a)
          See SpecialOperations.hexCases(Automaton).
 Automaton homomorph(char[] source, char[] dest)
          See SpecialOperations.homomorph(Automaton, char[], char[]).
 Automaton intersection(Automaton a)
          See BasicOperations.intersection(Automaton, Automaton).
 boolean isDeterministic()
          Returns deterministic flag for this automaton.
 boolean isEmpty()
          See BasicOperations.isEmpty(Automaton).
 boolean isEmptyString()
          See BasicOperations.isEmptyString(Automaton).
 boolean isFinite()
          See SpecialOperations.isFinite(Automaton).
 boolean isTotal()
          See BasicOperations.isTotal(Automaton).
static Automaton load(java.io.InputStream stream)
          Retrieves a serialized Automaton from a stream.
static Automaton load(java.net.URL url)
          Retrieves a serialized Automaton located by a URL.
static Automaton makeAnyChar()
          See BasicAutomata.makeAnyChar().
static Automaton makeAnyString()
          See BasicAutomata.makeAnyString().
static Automaton makeChar(char c)
          See BasicAutomata.makeChar(char).
static Automaton makeCharRange(char min, char max)
          See BasicAutomata.makeCharRange(char, char).
static Automaton makeCharSet(java.lang.String set)
          See BasicAutomata.makeCharSet(String).
static Automaton makeDecimalValue(java.lang.String value)
          See BasicAutomata.makeDecimalValue(String).
static Automaton makeEmpty()
          See BasicAutomata.makeEmpty().
static Automaton makeEmptyString()
          See BasicAutomata.makeEmptyString().
static Automaton makeFractionDigits(int i)
          See BasicAutomata.makeFractionDigits(int).
static Automaton makeIntegerValue(java.lang.String value)
          See BasicAutomata.makeIntegerValue(String).
static Automaton makeInterval(int min, int max, int digits)
          See BasicAutomata.makeInterval(int, int, int).
static Automaton makeMaxInteger(java.lang.String n)
          See BasicAutomata.makeMaxInteger(String).
static Automaton makeMinInteger(java.lang.String n)
          See BasicAutomata.makeMinInteger(String).
static Automaton makeString(java.lang.String s)
          See BasicAutomata.makeString(String).
static Automaton makeStringMatcher(java.lang.String s)
          See BasicAutomata.makeStringMatcher(String).
static Automaton makeTotalDigits(int i)
          See BasicAutomata.makeTotalDigits(int).
 void minimize()
          See MinimizationOperations.minimize(Automaton).
static Automaton minimize(Automaton a)
          See MinimizationOperations.minimize(Automaton).
 Automaton minus(Automaton a)
          See BasicOperations.minus(Automaton, Automaton).
 Automaton optional()
          See BasicOperations.optional(Automaton).
 Automaton overlap(Automaton a)
          See SpecialOperations.overlap(Automaton, Automaton).
 void prefixClose()
          See SpecialOperations.prefixClose(Automaton).
 Automaton projectChars(java.util.Set<java.lang.Character> chars)
          See SpecialOperations.projectChars(Automaton, Set).
 void reduce()
          Reduces this automaton.
 void removeDeadTransitions()
          Removes transitions to dead states and calls reduce() and clearHashCode().
 Automaton repeat()
          See BasicOperations.repeat(Automaton).
 Automaton repeat(int min)
          See BasicOperations.repeat(Automaton, int).
 Automaton repeat(int min, int max)
          See BasicOperations.repeat(Automaton, int, int).
static Automaton replaceWhitespace(Automaton a)
          See SpecialOperations.replaceWhitespace(Automaton).
 void restoreInvariant()
          Restores representation invariant.
 boolean run(java.lang.String s)
          See BasicOperations.run(Automaton, String).
static boolean setAllowMutate(boolean flag)
          Sets or resets allow mutate flag.
 void setDeterministic(boolean deterministic)
          Sets deterministic flag for this automaton.
 void setInfo(java.lang.Object info)
          Associates extra information with this automaton.
 void setInitialState(State s)
          Sets initial state.
static void setMinimization(int algorithm)
          Selects minimization algorithm (default: MINIMIZE_HOPCROFT).
static void setMinimizeAlways(boolean flag)
          Sets or resets minimize always flag.
 Automaton shuffle(Automaton a)
          See ShuffleOperations.shuffle(Automaton, Automaton).
static java.lang.String shuffleSubsetOf(java.util.Collection<Automaton> ca, Automaton a, java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle)
          See ShuffleOperations.shuffleSubsetOf(Collection, Automaton, Character, Character).
 Automaton singleChars()
          See SpecialOperations.singleChars(Automaton).
 void store(java.io.OutputStream stream)
          Writes this Automaton to the given stream.
 boolean subsetOf(Automaton a)
          See BasicOperations.subsetOf(Automaton, Automaton).
 Automaton subst(char c, java.lang.String s)
          See SpecialOperations.subst(Automaton, char, String).
 Automaton subst(java.util.Map<java.lang.Character,java.util.Set<java.lang.Character>> map)
          See SpecialOperations.subst(Automaton, Map).
 java.lang.String toDot()
          Returns Graphviz Dot representation of this automaton.
 java.lang.String toString()
          Returns a string representation of this automaton.
 Automaton trim(java.lang.String set, char c)
          See SpecialOperations.trim(Automaton, String, char).
 Automaton union(Automaton a)
          See BasicOperations.union(Automaton, Automaton).
static Automaton union(java.util.Collection<Automaton> l)
          See BasicOperations.union(Collection).
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

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:
setMinimization(int), Constant Field Values

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:
setMinimization(int), Constant Field Values

MINIMIZE_HUFFMAN

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

See Also:
setMinimization(int), Constant Field Values
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), State, Transition
Method Detail

addEpsilons

public void addEpsilons(java.util.Collection<StatePair> pairs)
See BasicOperations.addEpsilons(Automaton, Collection).


clone

public Automaton clone()
Returns a clone of this automaton.

Overrides:
clone in class java.lang.Object

complement

public Automaton complement()
See BasicOperations.complement(Automaton).


compress

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


concatenate

public Automaton concatenate(Automaton a)
See BasicOperations.concatenate(Automaton, Automaton).


concatenate

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


determinize

public void determinize()
See BasicOperations.determinize(Automaton).


equals

public boolean equals(java.lang.Object obj)
Returns true if the language of this automaton is equal to the language of the given automaton. Implemented using hashCode and subsetOf.

Overrides:
equals in class java.lang.Object

expandSingleton

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


getAcceptStates

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

Returns:
set of State objects

getCommonPrefix

public java.lang.String getCommonPrefix()
See SpecialOperations.getCommonPrefix(Automaton).


getFiniteStrings

public java.util.Set<java.lang.String> getFiniteStrings()
See SpecialOperations.getFiniteStrings(Automaton).


getFiniteStrings

public java.util.Set<java.lang.String> getFiniteStrings(int limit)
See SpecialOperations.getFiniteStrings(Automaton, int).


getInfo

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

Returns:
extra information
See Also:
setInfo(Object)

getInitialState

public State getInitialState()
Gets initial state.

Returns:
state

getLiveStates

public java.util.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 java.lang.String getShortestExample(boolean accepted)
See BasicOperations.getShortestExample(Automaton, boolean).


getSingleton

public java.lang.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 java.util.Set<State> getStates()
Returns the set of states that are reachable from the initial state.

Returns:
set of State objects

getStrings

public java.util.Set<java.lang.String> getStrings(int length)
See SpecialOperations.getStrings(Automaton, int).


hashCode

public int hashCode()
Returns hash code for this automaton. The hash code is based on the number of states and transitions in the minimized automaton. Invoking this method may involve minimizing the automaton.

Overrides:
hashCode in class java.lang.Object

hexCases

public static Automaton hexCases(Automaton a)
See SpecialOperations.hexCases(Automaton).


homomorph

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


intersection

public Automaton intersection(Automaton a)
See BasicOperations.intersection(Automaton, Automaton).


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 BasicOperations.isEmpty(Automaton).


isEmptyString

public boolean isEmptyString()
See BasicOperations.isEmptyString(Automaton).


isFinite

public boolean isFinite()
See SpecialOperations.isFinite(Automaton).


isTotal

public boolean isTotal()
See BasicOperations.isTotal(Automaton).


load

public static Automaton load(java.io.InputStream stream)
                      throws java.io.IOException,
                             java.io.OptionalDataException,
                             java.lang.ClassCastException,
                             java.lang.ClassNotFoundException,
                             java.io.InvalidClassException
Retrieves a serialized Automaton from a stream.

Parameters:
stream - input stream with serialized automaton
Throws:
java.io.IOException - if input/output related exception occurs
java.io.OptionalDataException - if the data is not a serialized object
java.io.InvalidClassException - if the class serial number does not match
java.lang.ClassCastException - if the data is not a serialized Automaton
java.lang.ClassNotFoundException - if the class of the serialized object cannot be found

load

public static Automaton load(java.net.URL url)
                      throws java.io.IOException,
                             java.io.OptionalDataException,
                             java.lang.ClassCastException,
                             java.lang.ClassNotFoundException,
                             java.io.InvalidClassException
Retrieves a serialized Automaton located by a URL.

Parameters:
url - URL of serialized automaton
Throws:
java.io.IOException - if input/output related exception occurs
java.io.OptionalDataException - if the data is not a serialized object
java.io.InvalidClassException - if the class serial number does not match
java.lang.ClassCastException - if the data is not a serialized Automaton
java.lang.ClassNotFoundException - if the class of the serialized object cannot be found

makeAnyChar

public static Automaton makeAnyChar()
See BasicAutomata.makeAnyChar().


makeAnyString

public static Automaton makeAnyString()
See BasicAutomata.makeAnyString().


makeChar

public static Automaton makeChar(char c)
See BasicAutomata.makeChar(char).


makeCharRange

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


makeCharSet

public static Automaton makeCharSet(java.lang.String set)
See BasicAutomata.makeCharSet(String).


makeDecimalValue

public static Automaton makeDecimalValue(java.lang.String value)
See BasicAutomata.makeDecimalValue(String).


makeEmpty

public static Automaton makeEmpty()
See BasicAutomata.makeEmpty().


makeEmptyString

public static Automaton makeEmptyString()
See BasicAutomata.makeEmptyString().


makeFractionDigits

public static Automaton makeFractionDigits(int i)
See BasicAutomata.makeFractionDigits(int).


makeIntegerValue

public static Automaton makeIntegerValue(java.lang.String value)
See BasicAutomata.makeIntegerValue(String).


makeInterval

public static Automaton makeInterval(int min,
                                     int max,
                                     int digits)
                              throws java.lang.IllegalArgumentException
See BasicAutomata.makeInterval(int, int, int).

Throws:
java.lang.IllegalArgumentException

makeMaxInteger

public static Automaton makeMaxInteger(java.lang.String n)
See BasicAutomata.makeMaxInteger(String).


makeMinInteger

public static Automaton makeMinInteger(java.lang.String n)
See BasicAutomata.makeMinInteger(String).


makeString

public static Automaton makeString(java.lang.String s)
See BasicAutomata.makeString(String).


makeStringMatcher

public static Automaton makeStringMatcher(java.lang.String s)
See BasicAutomata.makeStringMatcher(String).


makeTotalDigits

public static Automaton makeTotalDigits(int i)
See BasicAutomata.makeTotalDigits(int).


minimize

public void minimize()
See MinimizationOperations.minimize(Automaton).


minimize

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


minus

public Automaton minus(Automaton a)
See BasicOperations.minus(Automaton, Automaton).


optional

public Automaton optional()
See BasicOperations.optional(Automaton).


overlap

public Automaton overlap(Automaton a)
See SpecialOperations.overlap(Automaton, Automaton).


prefixClose

public void prefixClose()
See SpecialOperations.prefixClose(Automaton).


projectChars

public Automaton projectChars(java.util.Set<java.lang.Character> chars)
See SpecialOperations.projectChars(Automaton, Set).


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 BasicOperations.repeat(Automaton).


repeat

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


repeat

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


replaceWhitespace

public static Automaton replaceWhitespace(Automaton a)
See SpecialOperations.replaceWhitespace(Automaton).


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:
setDeterministic(boolean)

run

public boolean run(java.lang.String s)
See BasicOperations.run(Automaton, String).


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(java.lang.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.shuffle(Automaton, Automaton).


shuffleSubsetOf

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


singleChars

public Automaton singleChars()
See SpecialOperations.singleChars(Automaton).


store

public void store(java.io.OutputStream stream)
           throws java.io.IOException
Writes this Automaton to the given stream.

Parameters:
stream - output stream for serialized automaton
Throws:
java.io.IOException - if input/output related exception occurs

subsetOf

public boolean subsetOf(Automaton a)
See BasicOperations.subsetOf(Automaton, Automaton).


subst

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


subst

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


toDot

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


toString

public java.lang.String toString()
Returns a string representation of this automaton.

Overrides:
toString in class java.lang.Object

trim

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


union

public Automaton union(Automaton a)
See BasicOperations.union(Automaton, Automaton).


union

public static Automaton union(java.util.Collection<Automaton> l)
See BasicOperations.union(Collection).



Copyright © 2001-2008 Anders Møller.