public class Automaton extends Object implements Serializable, Cloneable
Class invariants:
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.)
reduce()
)
and have no transitions to dead states (see removeDeadTransitions()
).
isDeterministic()
returns false (but
the converse is not required).
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.
Modifier and Type | Field and Description |
---|---|
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.
|
Constructor and Description |
---|
Automaton()
Constructs a new automaton that accepts the empty language.
|
Modifier and Type | Method and Description |
---|---|
void |
addEpsilons(Collection<StatePair> pairs)
|
Automaton |
clone()
Returns a clone of this automaton.
|
Automaton |
complement()
|
Automaton |
compress(String set,
char c)
|
Automaton |
concatenate(Automaton a)
|
static Automaton |
concatenate(List<Automaton> l)
|
void |
determinize()
|
boolean |
equals(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.
|
Set<State> |
getAcceptStates()
Returns the set of reachable accept states.
|
String |
getCommonPrefix()
|
Set<String> |
getFiniteStrings()
|
Set<String> |
getFiniteStrings(int limit)
|
Object |
getInfo()
Returns extra information associated with this automaton.
|
State |
getInitialState()
Gets initial state.
|
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.
|
String |
getShortestExample(boolean accepted)
|
String |
getSingleton()
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)
|
int |
hashCode()
Returns hash code for this automaton.
|
static Automaton |
hexCases(Automaton a)
|
Automaton |
homomorph(char[] source,
char[] dest)
|
Automaton |
intersection(Automaton a)
|
boolean |
isDeterministic()
Returns deterministic flag for this automaton.
|
boolean |
isEmpty()
|
boolean |
isEmptyString()
|
boolean |
isFinite()
|
boolean |
isTotal()
|
static Automaton |
load(InputStream stream)
Retrieves a serialized
Automaton from a stream. |
static Automaton |
load(URL url)
Retrieves a serialized
Automaton 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(String set)
|
static Automaton |
makeDecimalValue(String value)
|
static Automaton |
makeEmpty()
|
static Automaton |
makeEmptyString()
|
static Automaton |
makeFractionDigits(int i)
|
static Automaton |
makeIntegerValue(String value)
|
static Automaton |
makeInterval(int min,
int max,
int digits)
|
static Automaton |
makeMaxInteger(String n)
|
static Automaton |
makeMinInteger(String n)
|
static Automaton |
makeString(String s)
|
static Automaton |
makeStringMatcher(String s)
|
static Automaton |
makeStringUnion(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(Set<Character> chars)
|
void |
reduce()
Reduces this automaton.
|
void |
removeDeadTransitions()
Removes transitions to dead states and calls
reduce() and clearHashCode() . |
Automaton |
repeat()
|
Automaton |
repeat(int min)
|
Automaton |
repeat(int min,
int max)
|
static Automaton |
replaceWhitespace(Automaton a)
|
void |
restoreInvariant()
Restores representation invariant.
|
boolean |
run(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(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)
|
static String |
shuffleSubsetOf(Collection<Automaton> ca,
Automaton a,
Character suspend_shuffle,
Character resume_shuffle)
|
Automaton |
singleChars()
|
void |
store(OutputStream stream)
Writes this
Automaton to the given stream. |
boolean |
subsetOf(Automaton a)
|
Automaton |
subst(char c,
String s)
|
Automaton |
subst(Map<Character,Set<Character>> map)
|
String |
toDot()
Returns Graphviz Dot
representation of this automaton.
|
String |
toString()
Returns a string representation of this automaton.
|
Automaton |
trim(String set,
char c)
|
Automaton |
union(Automaton a)
|
static Automaton |
union(Collection<Automaton> l)
|
public static final int MINIMIZE_BRZOZOWSKI
setMinimization(int)
,
Constant Field Valuespublic static final int MINIMIZE_HOPCROFT
setMinimization(int)
,
Constant Field Valuespublic static final int MINIMIZE_HUFFMAN
setMinimization(int)
,
Constant Field Valuespublic static final int MINIMIZE_VALMARI
setMinimization(int)
,
Constant Field Valuespublic Automaton()
State
and Transition
objects.setInitialState(State)
,
State
,
Transition
public void addEpsilons(Collection<StatePair> pairs)
public Automaton complement()
public void determinize()
public boolean equals(Object obj)
hashCode
and
subsetOf
.public void expandSingleton()
public Set<State> getAcceptStates()
State
objectspublic String getCommonPrefix()
public Object getInfo()
setInfo(Object)
public State getInitialState()
public Set<State> getLiveStates()
State
objectspublic int getNumberOfStates()
public int getNumberOfTransitions()
public String getShortestExample(boolean accepted)
public String getSingleton()
public Set<State> getStates()
State
objectspublic int hashCode()
public Automaton homomorph(char[] source, char[] dest)
public boolean isDeterministic()
public boolean isEmpty()
public boolean isEmptyString()
public boolean isFinite()
public boolean isTotal()
public static Automaton load(InputStream stream) throws IOException, ClassCastException, ClassNotFoundException
Automaton
from a stream.stream
- input stream with serialized automatonIOException
- if input/output related exception occursClassCastException
- if the data is not a serialized Automaton
ClassNotFoundException
- if the class of the serialized object cannot be foundpublic static Automaton load(URL url) throws IOException, ClassCastException, ClassNotFoundException
Automaton
located by a URL.url
- URL of serialized automatonIOException
- if input/output related exception occursClassCastException
- if the data is not a serialized Automaton
ClassNotFoundException
- if the class of the serialized object cannot be foundpublic static Automaton makeAnyChar()
public static Automaton makeAnyString()
public static Automaton makeChar(char c)
public static Automaton makeCharRange(char min, char max)
public static Automaton makeEmpty()
public static Automaton makeEmptyString()
public static Automaton makeFractionDigits(int i)
public static Automaton makeInterval(int min, int max, int digits) throws IllegalArgumentException
IllegalArgumentException
public static Automaton makeStringUnion(CharSequence... strings)
public static Automaton makeTotalDigits(int i)
public void minimize()
public static Automaton minimize(Automaton a)
MinimizationOperations.minimize(Automaton)
.
Returns the automaton being given as argument.public Automaton optional()
public void prefixClose()
public void reduce()
public void removeDeadTransitions()
reduce()
and clearHashCode()
.
(A state is "dead" if no accept state is reachable from it.)public Automaton repeat()
public Automaton repeat(int min)
public Automaton repeat(int min, int max)
public void restoreInvariant()
setDeterministic(boolean)
public boolean run(String s)
public static boolean setAllowMutate(boolean flag)
flag
- if true, the flag is setpublic void setDeterministic(boolean deterministic)
deterministic
- true if the automaton is definitely deterministic, false if the automaton
may be nondeterministicpublic void setInfo(Object info)
info
- extra informationpublic void setInitialState(State s)
s
- statepublic static void setMinimization(int algorithm)
MINIMIZE_HOPCROFT
).algorithm
- minimization algorithmpublic static void setMinimizeAlways(boolean flag)
minimize()
will automatically
be invoked after all operations that otherwise may produce non-minimal automata.
By default, the flag is not set.flag
- if true, the flag is setpublic static String shuffleSubsetOf(Collection<Automaton> ca, Automaton a, Character suspend_shuffle, Character resume_shuffle)
public Automaton singleChars()
public void store(OutputStream stream) throws IOException
Automaton
to the given stream.stream
- output stream for serialized automatonIOException
- if input/output related exception occurspublic boolean subsetOf(Automaton a)
public String toDot()
public String toString()
public static Automaton union(Collection<Automaton> l)
Copyright © 2001-2017 Anders Møller.