Package 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
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()
andsetDeterministic(boolean)
methods should be used afterwards to restore representation invariants that are assumed by the built-in automata operations.- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description (package private) static boolean
allow_mutation
Selects whether operations may modify the input automata (default:false
).(package private) boolean
deterministic
If true, then this automaton is definitely deterministic (i.e., there are no choices for any run, but a run may crash).(package private) int
hash_code
Hash code.(package private) java.lang.Object
info
Extra data associated with this automaton.(package private) State
initial
Initial state of this automaton.(package private) static java.lang.Boolean
is_debug
Caches theisDebug
state.(package private) static int
minimization
Selects minimization algorithm (default:MINIMIZE_HOPCROFT
).(package private) static boolean
minimize_always
Minimize always flag.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.static int
MINIMIZE_VALMARI
Minimize using Valmari's O(n + m log m) algorithm.(package private) static long
serialVersionUID
(package private) java.lang.String
singleton
Singleton string.
-
Constructor Summary
Constructors Constructor Description Automaton()
Constructs a new automaton that accepts the empty language.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addEpsilons(java.util.Collection<StatePair> pairs)
(package private) void
checkMinimizeAlways()
(package private) void
clearHashCode()
Must be invoked when the stored hash code may no longer be valid.Automaton
clone()
Returns a clone of this automaton.(package private) Automaton
cloneExpanded()
Returns a clone of this automaton, expands if singleton.(package private) Automaton
cloneExpandedIfRequired()
Returns a clone of this automaton unlessallow_mutation
is set, expands if singleton.(package private) Automaton
cloneIfRequired()
Returns a clone of this automaton, or this automaton itself ifallow_mutation
flag is set.Automaton
complement()
Automaton
compress(java.lang.String set, char c)
Automaton
concatenate(Automaton a)
static Automaton
concatenate(java.util.List<Automaton> l)
void
determinize()
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.(package private) static boolean
getAllowMutate()
Returns the state of the allow mutate flag.java.lang.String
getCommonPrefix()
java.util.Set<java.lang.String>
getFiniteStrings()
java.util.Set<java.lang.String>
getFiniteStrings(int limit)
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.private java.util.Set<State>
getLiveStates(java.util.Set<State> 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)
java.lang.String
getSingleton()
Returns the singleton string for this automaton.(package private) static Transition[][]
getSortedTransitions(java.util.Set<State> states)
Returns a sorted array of transitions for each state (and sets state numbers).(package private) char[]
getStartPoints()
Returns sorted array of all interval start points.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)
int
hashCode()
Returns hash code for this automaton.static Automaton
hexCases(Automaton a)
Automaton
homomorph(char[] source, char[] dest)
Automaton
intersection(Automaton a)
(package private) boolean
isDebug()
boolean
isDeterministic()
Returns deterministic flag for this automaton.boolean
isEmpty()
boolean
isEmptyString()
boolean
isFinite()
(package private) boolean
isSingleton()
boolean
isTotal()
static Automaton
load(java.io.InputStream stream)
Retrieves a serializedAutomaton
from a stream.static Automaton
load(java.net.URL url)
Retrieves a serializedAutomaton
located by a URL.static Automaton
makeAnyChar()
static Automaton
makeAnyString()
static Automaton
makeChar(char c)
static Automaton
makeCharRange(char min, char max)
static Automaton
makeCharSet(java.lang.String set)
static Automaton
makeDecimalValue(java.lang.String value)
static Automaton
makeEmpty()
static Automaton
makeEmptyString()
static Automaton
makeFractionDigits(int i)
static Automaton
makeIntegerValue(java.lang.String value)
static Automaton
makeInterval(int min, int max, int digits)
static Automaton
makeMaxInteger(java.lang.String n)
static Automaton
makeMinInteger(java.lang.String n)
static Automaton
makeString(java.lang.String s)
static Automaton
makeStringMatcher(java.lang.String s)
static Automaton
makeStringUnion(java.lang.CharSequence... strings)
static Automaton
makeTotalDigits(int i)
void
minimize()
static Automaton
minimize(Automaton a)
Automaton
minus(Automaton a)
Automaton
optional()
Automaton
overlap(Automaton a)
void
prefixClose()
Automaton
projectChars(java.util.Set<java.lang.Character> chars)
(package private) void
recomputeHashCode()
Recomputes the hash code.void
reduce()
Reduces this automaton.void
removeDeadTransitions()
Removes transitions to dead states and callsreduce()
andclearHashCode()
.Automaton
repeat()
Automaton
repeat(int min)
Automaton
repeat(int min, int max)
static Automaton
replaceWhitespace(Automaton a)
void
restoreInvariant()
Restores representation invariant.boolean
run(java.lang.String s)
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.(package private) static void
setStateNumbers(java.util.Set<State> states)
Assigns consecutive numbers to the given states.Automaton
shuffle(Automaton a)
static java.lang.String
shuffleSubsetOf(java.util.Collection<Automaton> ca, Automaton a, java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle)
Automaton
singleChars()
void
store(java.io.OutputStream stream)
Writes thisAutomaton
to the given stream.boolean
subsetOf(Automaton a)
Automaton
subst(char c, java.lang.String s)
Automaton
subst(java.util.Map<java.lang.Character,java.util.Set<java.lang.Character>> map)
java.lang.String
toDot()
Returns Graphviz Dot representation of this automaton.java.lang.String
toString()
Returns a string representation of this automaton.(package private) void
totalize()
Adds transitions to explicit crash state to ensure that transition function is total.Automaton
trim(java.lang.String set, char c)
Automaton
union(Automaton a)
static Automaton
union(java.util.Collection<Automaton> l)
-
-
-
Field Detail
-
serialVersionUID
static final long serialVersionUID
- See Also:
- 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
-
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_VALMARI
public static final int MINIMIZE_VALMARI
Minimize using Valmari's O(n + m log m) algorithm.- See Also:
setMinimization(int)
, Constant Field Values
-
minimization
static int minimization
Selects minimization algorithm (default:MINIMIZE_HOPCROFT
).
-
initial
State initial
Initial state of this automaton.
-
deterministic
boolean deterministic
If true, then this automaton is definitely deterministic (i.e., there are no choices for any run, but a run may crash).
-
info
transient java.lang.Object info
Extra data associated with this automaton.
-
hash_code
int hash_code
Hash code. Recomputed byminimize()
.
-
singleton
java.lang.String singleton
Singleton string. Null if not applicable.
-
minimize_always
static boolean minimize_always
Minimize always flag.
-
allow_mutation
static boolean allow_mutation
Selects whether operations may modify the input automata (default:false
).
-
is_debug
static java.lang.Boolean is_debug
Caches theisDebug
state.
-
-
Constructor Detail
-
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:
setInitialState(State)
,State
,Transition
-
-
Method Detail
-
isDebug
boolean isDebug()
-
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
-
getAllowMutate
static boolean getAllowMutate()
Returns the state of the 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.- Returns:
- current value of the flag
-
checkMinimizeAlways
void checkMinimizeAlways()
-
isSingleton
boolean isSingleton()
-
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.
-
setInitialState
public void setInitialState(State s)
Sets initial state.- Parameters:
s
- state
-
getInitialState
public 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
public void setInfo(java.lang.Object info)
Associates extra information with this automaton.- Parameters:
info
- extra information
-
getInfo
public java.lang.Object getInfo()
Returns extra information associated with this automaton.- Returns:
- extra information
- See Also:
setInfo(Object)
-
getStates
public java.util.Set<State> getStates()
Returns the set of states that are reachable from the initial state.- Returns:
- set of
State
objects
-
getAcceptStates
public java.util.Set<State> getAcceptStates()
Returns the set of reachable accept states.- Returns:
- set of
State
objects
-
setStateNumbers
static void setStateNumbers(java.util.Set<State> states)
Assigns consecutive numbers to the given states.
-
totalize
void totalize()
Adds transitions to explicit crash state to ensure that transition function is total.
-
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)
-
reduce
public void reduce()
Reduces this automaton. An automaton is "reduced" by combining overlapping and adjacent edge intervals with same destination.
-
getStartPoints
char[] getStartPoints()
Returns sorted array of all interval start points.
-
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
-
removeDeadTransitions
public void removeDeadTransitions()
Removes transitions to dead states and callsreduce()
andclearHashCode()
. (A state is "dead" if no accept state is reachable from it.)
-
getSortedTransitions
static Transition[][] getSortedTransitions(java.util.Set<State> states)
Returns a sorted array of transitions for each state (and sets state numbers).
-
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
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 usinghashCode
andsubsetOf
.- Overrides:
equals
in classjava.lang.Object
-
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 classjava.lang.Object
-
recomputeHashCode
void recomputeHashCode()
Recomputes the hash code. The automaton must be minimal when this operation is performed.
-
clearHashCode
void clearHashCode()
Must be invoked when the stored hash code may no longer be valid.
-
toString
public java.lang.String toString()
Returns a string representation of this automaton.- Overrides:
toString
in classjava.lang.Object
-
toDot
public java.lang.String toDot()
Returns Graphviz Dot representation of this automaton.
-
cloneExpanded
Automaton cloneExpanded()
Returns a clone of this automaton, expands if singleton.
-
cloneExpandedIfRequired
Automaton cloneExpandedIfRequired()
Returns a clone of this automaton unlessallow_mutation
is set, expands if singleton.
-
clone
public Automaton clone()
Returns a clone of this automaton.- Overrides:
clone
in classjava.lang.Object
-
cloneIfRequired
Automaton cloneIfRequired()
Returns a clone of this automaton, or this automaton itself ifallow_mutation
flag is set.
-
load
public static Automaton load(java.net.URL url) throws java.io.IOException, java.lang.ClassCastException, java.lang.ClassNotFoundException
Retrieves a serializedAutomaton
located by a URL.- Parameters:
url
- URL of serialized automaton- Throws:
java.io.IOException
- if input/output related exception occursjava.lang.ClassCastException
- if the data is not a serializedAutomaton
java.lang.ClassNotFoundException
- if the class of the serialized object cannot be found
-
load
public static Automaton load(java.io.InputStream stream) throws java.io.IOException, java.lang.ClassCastException, java.lang.ClassNotFoundException
Retrieves a serializedAutomaton
from a stream.- Parameters:
stream
- input stream with serialized automaton- Throws:
java.io.IOException
- if input/output related exception occursjava.lang.ClassCastException
- if the data is not a serializedAutomaton
java.lang.ClassNotFoundException
- if the class of the serialized object cannot be found
-
store
public void store(java.io.OutputStream stream) throws java.io.IOException
Writes thisAutomaton
to the given stream.- Parameters:
stream
- output stream for serialized automaton- Throws:
java.io.IOException
- if input/output related exception occurs
-
makeEmpty
public static Automaton makeEmpty()
-
makeEmptyString
public static Automaton makeEmptyString()
-
makeAnyString
public static Automaton makeAnyString()
-
makeAnyChar
public static Automaton makeAnyChar()
-
makeChar
public static Automaton makeChar(char c)
-
makeCharRange
public static Automaton makeCharRange(char min, char max)
-
makeCharSet
public static Automaton makeCharSet(java.lang.String set)
-
makeInterval
public static Automaton makeInterval(int min, int max, int digits) throws java.lang.IllegalArgumentException
- Throws:
java.lang.IllegalArgumentException
-
makeString
public static Automaton makeString(java.lang.String s)
-
makeStringUnion
public static Automaton makeStringUnion(java.lang.CharSequence... strings)
-
makeMaxInteger
public static Automaton makeMaxInteger(java.lang.String n)
-
makeMinInteger
public static Automaton makeMinInteger(java.lang.String n)
-
makeTotalDigits
public static Automaton makeTotalDigits(int i)
-
makeFractionDigits
public static Automaton makeFractionDigits(int i)
-
makeIntegerValue
public static Automaton makeIntegerValue(java.lang.String value)
-
makeDecimalValue
public static Automaton makeDecimalValue(java.lang.String value)
-
makeStringMatcher
public static Automaton makeStringMatcher(java.lang.String s)
-
optional
public Automaton optional()
-
repeat
public Automaton repeat()
-
repeat
public Automaton repeat(int min)
-
repeat
public Automaton repeat(int min, int max)
-
complement
public Automaton complement()
-
subsetOf
public boolean subsetOf(Automaton a)
-
determinize
public void determinize()
-
addEpsilons
public void addEpsilons(java.util.Collection<StatePair> pairs)
-
isEmptyString
public boolean isEmptyString()
-
isEmpty
public boolean isEmpty()
-
isTotal
public boolean isTotal()
-
getShortestExample
public java.lang.String getShortestExample(boolean accepted)
-
run
public boolean run(java.lang.String s)
-
minimize
public void minimize()
-
minimize
public static Automaton minimize(Automaton a)
SeeMinimizationOperations.minimize(Automaton)
. Returns the automaton being given as argument.
-
singleChars
public Automaton singleChars()
-
trim
public Automaton trim(java.lang.String set, char c)
-
compress
public Automaton compress(java.lang.String set, char c)
-
subst
public Automaton subst(java.util.Map<java.lang.Character,java.util.Set<java.lang.Character>> map)
-
subst
public Automaton subst(char c, java.lang.String s)
-
homomorph
public Automaton homomorph(char[] source, char[] dest)
-
projectChars
public Automaton projectChars(java.util.Set<java.lang.Character> chars)
-
isFinite
public boolean isFinite()
-
getStrings
public java.util.Set<java.lang.String> getStrings(int length)
-
getFiniteStrings
public java.util.Set<java.lang.String> getFiniteStrings()
-
getFiniteStrings
public java.util.Set<java.lang.String> getFiniteStrings(int limit)
-
getCommonPrefix
public java.lang.String getCommonPrefix()
-
prefixClose
public void prefixClose()
-
shuffleSubsetOf
public static java.lang.String shuffleSubsetOf(java.util.Collection<Automaton> ca, Automaton a, java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle)
-
-