Package dk.brics.automaton
Class Automaton
java.lang.Object
dk.brics.automaton.Automaton
- All Implemented Interfaces:
Serializable
,Cloneable
Finite-state automaton with regular expression operations.
Class invariants:
- An automaton is either represented explicitly (with
State
andTransition
objects) or with a singleton string (seegetSingleton()
andexpandSingleton()
) 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 (seeremoveDeadTransitions()
). - 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:
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final int
Minimize using Brzozowski's O(2n) algorithm.static final int
Minimize using Hopcroft's O(n log n) algorithm.static final int
Minimize using Huffman's O(n2) algorithm. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
addEpsilons
(Collection<StatePair> pairs) clone()
Returns a clone of this automaton.static Automaton
concatenate
(List<Automaton> l) void
boolean
Returns true if the language of this automaton is equal to the language of the given automaton.void
Expands singleton representation to normal representation.Returns the set of reachable accept states.getFiniteStrings
(int limit) getInfo()
Returns extra information associated with this automaton.Gets initial state.Returns the set of live states.int
Returns the number of states in this automaton.int
Returns the number of transitions in this automaton.getShortestExample
(boolean accepted) Returns the singleton string for this automaton.Returns the set of states that are reachable from the initial state.getStrings
(int length) int
hashCode()
Returns hash code for this automaton.static Automaton
homomorph
(char[] source, char[] dest) boolean
Returns deterministic flag for this automaton.boolean
isEmpty()
boolean
boolean
isFinite()
boolean
isTotal()
static Automaton
load
(InputStream stream) Retrieves a serializedAutomaton
from a stream.static Automaton
Retrieves a serializedAutomaton
located by a URL.static Automaton
static Automaton
static Automaton
makeChar
(char c) static Automaton
makeCharRange
(char min, char max) static Automaton
makeCharSet
(String set) static Automaton
makeDecimalValue
(String value) static Automaton
static Automaton
static Automaton
makeFractionDigits
(int i) static Automaton
makeIntegerValue
(String value) static Automaton
makeInterval
(int min, int max, int digits) static Automaton
static Automaton
static Automaton
makeString
(String s) static Automaton
static Automaton
makeStringUnion
(CharSequence... strings) static Automaton
makeTotalDigits
(int i) void
minimize()
static Automaton
optional()
void
projectChars
(Set<Character> chars) void
reduce()
Reduces this automaton.void
Removes transitions to dead states and callsreduce()
andclearHashCode()
.repeat()
repeat
(int min) repeat
(int min, int max) static Automaton
void
Restores representation invariant.boolean
static boolean
setAllowMutate
(boolean flag) Sets or resets allow mutate flag.void
setDeterministic
(boolean deterministic) Sets deterministic flag for this automaton.void
Associates extra information with this automaton.void
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.static String
shuffleSubsetOf
(Collection<Automaton> ca, Automaton a, Character suspend_shuffle, Character resume_shuffle) void
store
(OutputStream stream) Writes thisAutomaton
to the given stream.boolean
toDot()
Returns Graphviz Dot representation of this automaton.toString()
Returns a string representation of this automaton.static Automaton
union
(Collection<Automaton> l)
-
Field Details
-
MINIMIZE_HUFFMAN
public static final int MINIMIZE_HUFFMANMinimize using Huffman's O(n2) algorithm. This is the standard text-book algorithm.- See Also:
-
MINIMIZE_BRZOZOWSKI
public static final int MINIMIZE_BRZOZOWSKIMinimize 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:
-
MINIMIZE_HOPCROFT
public static final int MINIMIZE_HOPCROFTMinimize using Hopcroft's O(n log n) algorithm. This is regarded as one of the most generally efficient algorithms that exist.- See Also:
-
-
Constructor Details
-
Automaton
public Automaton()Constructs a new automaton that accepts the empty language. Using this constructor, automata can be constructed manually fromState
andTransition
objects.- See Also:
-
-
Method Details
-
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, thenminimize()
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
-
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
-
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.
-
setInitialState
Sets initial state.- Parameters:
s
- state
-
getInitialState
Gets initial state.- Returns:
- state
-
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
-
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
Associates extra information with this automaton.- Parameters:
info
- extra information
-
getInfo
Returns extra information associated with this automaton.- Returns:
- extra information
- See Also:
-
getStates
Returns the set of states that are reachable from the initial state.- Returns:
- set of
State
objects
-
getAcceptStates
Returns the set of reachable accept states.- Returns:
- set of
State
objects
-
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:
-
reduce
public void reduce()Reduces this automaton. An automaton is "reduced" by combining overlapping and adjacent edge intervals with same destination. -
getLiveStates
Returns the set of live states. A state is "live" if an accept state is reachable from it.- Returns:
- set of
State
objects
-
removeDeadTransitions
public void removeDeadTransitions()Removes transitions to dead states and callsreduce()
andclearHashCode()
. (A state is "dead" if no accept state is reachable from it.) -
expandSingleton
public void expandSingleton()Expands singleton representation to normal representation. Does nothing if not in singleton representation. -
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. -
equals
Returns true if the language of this automaton is equal to the language of the given automaton. Implemented usinghashCode
andsubsetOf
. -
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. -
toString
Returns a string representation of this automaton. -
toDot
Returns Graphviz Dot representation of this automaton. -
clone
Returns a clone of this automaton. -
load
public static Automaton load(URL url) throws IOException, OptionalDataException, ClassCastException, ClassNotFoundException, InvalidClassException Retrieves a serializedAutomaton
located by a URL.- Parameters:
url
- URL of serialized automaton- Throws:
IOException
- if input/output related exception occursOptionalDataException
- if the data is not a serialized objectInvalidClassException
- if the class serial number does not matchClassCastException
- if the data is not a serializedAutomaton
ClassNotFoundException
- if the class of the serialized object cannot be found
-
load
public static Automaton load(InputStream stream) throws IOException, OptionalDataException, ClassCastException, ClassNotFoundException, InvalidClassException Retrieves a serializedAutomaton
from a stream.- Parameters:
stream
- input stream with serialized automaton- Throws:
IOException
- if input/output related exception occursOptionalDataException
- if the data is not a serialized objectInvalidClassException
- if the class serial number does not matchClassCastException
- if the data is not a serializedAutomaton
ClassNotFoundException
- if the class of the serialized object cannot be found
-
store
Writes thisAutomaton
to the given stream.- Parameters:
stream
- output stream for serialized automaton- Throws:
IOException
- if input/output related exception occurs
-
makeEmpty
-
makeEmptyString
-
makeAnyString
-
makeAnyChar
-
makeChar
-
makeCharRange
-
makeCharSet
-
makeInterval
- Throws:
IllegalArgumentException
-
makeString
-
makeStringUnion
-
makeMaxInteger
-
makeMinInteger
-
makeTotalDigits
-
makeFractionDigits
-
makeIntegerValue
-
makeDecimalValue
-
makeStringMatcher
-
concatenate
-
concatenate
-
optional
-
repeat
-
repeat
-
repeat
-
complement
-
minus
-
intersection
-
subsetOf
-
union
-
union
-
determinize
public void determinize() -
addEpsilons
-
isEmptyString
public boolean isEmptyString() -
isEmpty
public boolean isEmpty() -
isTotal
public boolean isTotal() -
getShortestExample
-
run
-
minimize
public void minimize() -
minimize
SeeMinimizationOperations.minimize(Automaton)
. Returns the automaton being given as argument. -
overlap
-
singleChars
-
trim
-
compress
-
subst
-
subst
-
homomorph
-
projectChars
-
isFinite
public boolean isFinite() -
getStrings
-
getFiniteStrings
-
getFiniteStrings
-
getCommonPrefix
-
prefixClose
public void prefixClose() -
hexCases
-
replaceWhitespace
-
shuffleSubsetOf
-
shuffle
-