|
|||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectdk.brics.automaton.BasicOperations
public final class BasicOperations
Basic automata operations.
Method Summary | |
---|---|
static void |
addEpsilons(Automaton a,
Collection<StatePair> pairs)
Adds epsilon transitions to the given automaton. |
static Automaton |
complement(Automaton a)
Returns a (deterministic) automaton that accepts the complement of the language of the given automaton. |
static Automaton |
concatenate(Automaton a1,
Automaton a2)
Returns an automaton that accepts the concatenation of the languages of the given automata. |
static Automaton |
concatenate(List<Automaton> l)
Returns an automaton that accepts the concatenation of the languages of the given automata. |
static void |
determinize(Automaton a)
Determinizes the given automaton. |
static String |
getShortestExample(Automaton a,
boolean accepted)
Returns a shortest accepted/rejected string. |
static Automaton |
intersection(Automaton a1,
Automaton a2)
Returns an automaton that accepts the intersection of the languages of the given automata. |
static boolean |
isEmpty(Automaton a)
Returns true if the given automaton accepts no strings. |
static boolean |
isEmptyString(Automaton a)
Returns true if the given automaton accepts the empty string and nothing else. |
static boolean |
isTotal(Automaton a)
Returns true if the given automaton accepts all strings. |
static Automaton |
minus(Automaton a1,
Automaton a2)
Returns a (deterministic) automaton that accepts the intersection of the language of a1 and the complement of the language of
a2 . |
static Automaton |
optional(Automaton a)
Returns an automaton that accepts the union of the empty string and the language of the given automaton. |
static Automaton |
repeat(Automaton a)
Returns an automaton that accepts the Kleene star (zero or more concatenated repetitions) of the language of the given automaton. |
static Automaton |
repeat(Automaton a,
int min)
Returns an automaton that accepts min or more
concatenated repetitions of the language of the given automaton. |
static Automaton |
repeat(Automaton a,
int min,
int max)
Returns an automaton that accepts between min and
max (including both) concatenated repetitions of the
language of the given automaton. |
static boolean |
run(Automaton a,
String s)
Returns true if the given string is accepted by the automaton. |
static boolean |
subsetOf(Automaton a1,
Automaton a2)
Returns true if the language of a1 is a subset of the
language of a2 . |
static Automaton |
union(Automaton a1,
Automaton a2)
Returns an automaton that accepts the union of the languages of the given automata. |
static Automaton |
union(Collection<Automaton> l)
Returns an automaton that accepts the union of the languages of the given automata. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Method Detail |
---|
public static void addEpsilons(Automaton a, Collection<StatePair> pairs)
pairs
- collection of StatePair
objects representing pairs of source/destination states
where epsilon transitions should be addedpublic static Automaton complement(Automaton a)
Complexity: linear in number of states (if already deterministic).
public static Automaton concatenate(Automaton a1, Automaton a2)
Complexity: linear in number of states.
public static Automaton concatenate(List<Automaton> l)
Complexity: linear in total number of states.
public static void determinize(Automaton a)
Complexity: exponential in number of states.
public static String getShortestExample(Automaton a, boolean accepted)
accepted
- if true, look for accepted strings; otherwise, look for rejected strings
public static Automaton intersection(Automaton a1, Automaton a2)
Complexity: quadratic in number of states.
public static boolean isEmpty(Automaton a)
public static boolean isEmptyString(Automaton a)
public static boolean isTotal(Automaton a)
public static Automaton minus(Automaton a1, Automaton a2)
a1
and the complement of the language of
a2
. As a side-effect, the automata may be determinized, if not
already deterministic.
Complexity: quadratic in number of states (if already deterministic).
public static Automaton optional(Automaton a)
Complexity: linear in number of states.
public static Automaton repeat(Automaton a)
Complexity: linear in number of states.
public static Automaton repeat(Automaton a, int min)
min
or more
concatenated repetitions of the language of the given automaton.
Complexity: linear in number of states and in min
.
public static Automaton repeat(Automaton a, int min, int max)
min
and
max
(including both) concatenated repetitions of the
language of the given automaton.
Complexity: linear in number of states and in min
and
max
.
public static boolean run(Automaton a, String s)
Complexity: linear in the length of the string.
Note: for full performance, use the RunAutomaton
class.
public static boolean subsetOf(Automaton a1, Automaton a2)
a1
is a subset of the
language of a2
.
As a side-effect, a2
is determinized if not already marked as
deterministic.
Complexity: quadratic in number of states.
public static Automaton union(Automaton a1, Automaton a2)
Complexity: linear in number of states.
public static Automaton union(Collection<Automaton> l)
Complexity: linear in number of states.
|
|||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |