Package dk.brics.automaton
Class ShuffleOperations
- java.lang.Object
-
- dk.brics.automaton.ShuffleOperations
-
public final class ShuffleOperations extends java.lang.Object
Automata operations involving shuffling.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
ShuffleOperations.ShuffleConfiguration
-
Constructor Summary
Constructors Modifier Constructor Description private
ShuffleOperations()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description private static void
add(java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle, java.util.LinkedList<ShuffleOperations.ShuffleConfiguration> pending, java.util.Set<ShuffleOperations.ShuffleConfiguration> visited, ShuffleOperations.ShuffleConfiguration c, int i1, Transition t1, Transition t2, char min, char max)
static Automaton
shuffle(Automaton a1, Automaton a2)
Returns an automaton that accepts the shuffle (interleaving) of the languages of the given automata.static java.lang.String
shuffleSubsetOf(java.util.Collection<Automaton> ca, Automaton a, java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle)
Returns a string that is an interleaving of strings that are accepted byca
but not bya
.
-
-
-
Method Detail
-
shuffle
public static Automaton shuffle(Automaton a1, Automaton a2)
Returns an automaton that accepts the shuffle (interleaving) of the languages of the given automata. As a side-effect, both automata are determinized, if not already deterministic. Never modifies the input automata languages.Complexity: quadratic in number of states (if already deterministic).
- Author:
- Torben Ruby <ruby@daimi.au.dk>
-
shuffleSubsetOf
public static java.lang.String shuffleSubsetOf(java.util.Collection<Automaton> ca, Automaton a, java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle)
Returns a string that is an interleaving of strings that are accepted byca
but not bya
. If no such string exists, null is returned. As a side-effect,a
is determinized, if not already deterministic. Only interleavings that respect the suspend/resume markers (two BMP private code points) are considered if the markers are non-null. Also, interleavings never split surrogate pairs.Complexity: proportional to the product of the numbers of states (if
a
is already deterministic).
-
add
private static void add(java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle, java.util.LinkedList<ShuffleOperations.ShuffleConfiguration> pending, java.util.Set<ShuffleOperations.ShuffleConfiguration> visited, ShuffleOperations.ShuffleConfiguration c, int i1, Transition t1, Transition t2, char min, char max)
-
-