public class Automaton
extends java.lang.Object
implements java.io.Serializable, java.lang.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.
|
Constructor and Description |
---|
Automaton()
Constructs a new automaton that accepts the empty language.
|
Modifier and Type | Method and Description |
---|---|
void |
addEpsilons(java.util.Collection<StatePair> pairs)
|
Automaton |
clone()
Returns a clone of this automaton.
|
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.
|
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.
|
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.
|
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)
|
boolean |
isDeterministic()
Returns deterministic flag for this automaton.
|
boolean |
isEmpty()
|
boolean |
isEmptyString()
|
boolean |
isFinite()
|
boolean |
isTotal()
|
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()
|
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)
|
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(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.
|
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 this
Automaton 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.
|
Automaton |
trim(java.lang.String set,
char c)
|
Automaton |
union(Automaton a)
|
static Automaton |
union(java.util.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 Automaton()
State
and Transition
objects.setInitialState(State)
,
State
,
Transition
public void addEpsilons(java.util.Collection<StatePair> pairs)
public Automaton clone()
clone
in class java.lang.Object
public Automaton complement()
public Automaton compress(java.lang.String set, char c)
public void determinize()
public boolean equals(java.lang.Object obj)
hashCode
and
subsetOf
.equals
in class java.lang.Object
public void expandSingleton()
public java.util.Set<State> getAcceptStates()
State
objectspublic java.lang.String getCommonPrefix()
public java.util.Set<java.lang.String> getFiniteStrings()
public java.util.Set<java.lang.String> getFiniteStrings(int limit)
public java.lang.Object getInfo()
setInfo(Object)
public State getInitialState()
public java.util.Set<State> getLiveStates()
State
objectspublic int getNumberOfStates()
public int getNumberOfTransitions()
public java.lang.String getShortestExample(boolean accepted)
public java.lang.String getSingleton()
public java.util.Set<State> getStates()
State
objectspublic java.util.Set<java.lang.String> getStrings(int length)
public int hashCode()
hashCode
in class java.lang.Object
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(java.io.InputStream stream) throws java.io.IOException, java.io.OptionalDataException, java.lang.ClassCastException, java.lang.ClassNotFoundException, java.io.InvalidClassException
Automaton
from a stream.stream
- input stream with serialized automatonjava.io.IOException
- if input/output related exception occursjava.io.OptionalDataException
- if the data is not a serialized objectjava.io.InvalidClassException
- if the class serial number does not matchjava.lang.ClassCastException
- if the data is not a serialized Automaton
java.lang.ClassNotFoundException
- if the class of the serialized object cannot be foundpublic static Automaton load(java.net.URL url) throws java.io.IOException, java.io.OptionalDataException, java.lang.ClassCastException, java.lang.ClassNotFoundException, java.io.InvalidClassException
Automaton
located by a URL.url
- URL of serialized automatonjava.io.IOException
- if input/output related exception occursjava.io.OptionalDataException
- if the data is not a serialized objectjava.io.InvalidClassException
- if the class serial number does not matchjava.lang.ClassCastException
- if the data is not a serialized Automaton
java.lang.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 makeCharSet(java.lang.String set)
public static Automaton makeDecimalValue(java.lang.String value)
public static Automaton makeEmpty()
public static Automaton makeEmptyString()
public static Automaton makeFractionDigits(int i)
public static Automaton makeIntegerValue(java.lang.String value)
public static Automaton makeInterval(int min, int max, int digits) throws java.lang.IllegalArgumentException
java.lang.IllegalArgumentException
public static Automaton makeMaxInteger(java.lang.String n)
public static Automaton makeMinInteger(java.lang.String n)
public static Automaton makeString(java.lang.String s)
public static Automaton makeStringMatcher(java.lang.String s)
public static Automaton makeStringUnion(java.lang.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 Automaton projectChars(java.util.Set<java.lang.Character> chars)
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(java.lang.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(java.lang.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 java.lang.String shuffleSubsetOf(java.util.Collection<Automaton> ca, Automaton a, java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle)
public Automaton singleChars()
public void store(java.io.OutputStream stream) throws java.io.IOException
Automaton
to the given stream.stream
- output stream for serialized automatonjava.io.IOException
- if input/output related exception occurspublic boolean subsetOf(Automaton a)
public Automaton subst(char c, java.lang.String s)
public Automaton subst(java.util.Map<java.lang.Character,java.util.Set<java.lang.Character>> map)
public java.lang.String toDot()
public java.lang.String toString()
toString
in class java.lang.Object
public Automaton trim(java.lang.String set, char c)
Copyright © 2001-2011 Anders Møller.