dk.brics.automaton
public final class BasicOperations extends Object
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.
|
Parameters: pairs collection of StatePair objects representing pairs of source/destination states where epsilon transitions should be added
Complexity: linear in number of states (if already deterministic).
Complexity: linear in number of states.
Complexity: linear in total number of states.
Complexity: exponential in number of states.
Parameters: accepted if true, look for accepted strings; otherwise, look for rejected strings
Returns: the string, null if none found
Complexity: quadratic in number of states.
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).
Complexity: linear in number of states.
Complexity: linear in number of states.
min
or more
concatenated repetitions of the language of the given automaton.
Complexity: linear in number of states and in min
.
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
.
Complexity: linear in the length of the string.
Note: for full performance, use the RunAutomaton class.
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.
Complexity: linear in number of states.
Complexity: linear in number of states.