dk.brics.automaton

Class ShuffleOperations

java.lang.Object

dk.brics.automaton.ShuffleOperations

public final class ShuffleOperations
extends Object

Automata operations involving shuffling.

Method Summary

Modifier and Type	Method and Description
static Automaton	shuffle(Automaton a1, Automaton a2) Returns an automaton that accepts the shuffle (interleaving) of the languages of the given automata.
static String	shuffleSubsetOf(Collection<Automaton> ca, Automaton a, Character suspend_shuffle, Character resume_shuffle) Returns a string that is an interleaving of strings that are accepted by ca but not by a.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 String shuffleSubsetOf(Collection<Automaton> ca,
                                     Automaton a,
                                     Character suspend_shuffle,
                                     Character resume_shuffle)

Returns a string that is an interleaving of strings that are accepted by ca but not by a. 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).