dk.brics.automaton
Class Automaton
java.lang.Object
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:
- An automaton is either represented explicitly (with
State
and Transition
objects)
or with a singleton string (see getSingleton()
and expandSingleton()
) in case the automaton is known to accept exactly one string.
(Implicitly, all states and transitions of an automaton are reachable from its initial state.)
- Automata are always reduced (see
reduce()
)
and have no transitions to dead states (see removeDeadTransitions()
).
- If an automaton is nondeterministic, then
isDeterministic()
returns false (but
the converse is not required).
- Automata provided as input to operations are generally assumed to be disjoint.
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@cs.au.dk>
- See Also:
- Serialized Form
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 |
makeStringUnion(java.lang.CharSequence... strings)
See BasicAutomata.makeStringUnion(CharSequence...) . |
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 |
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
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
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)
.
makeStringUnion
public static Automaton makeStringUnion(java.lang.CharSequence... strings)
- See
BasicAutomata.makeStringUnion(CharSequence...)
.
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-2011 Anders Møller.