Class ShuffleOperations

java.lang.Object
dk.brics.automaton.ShuffleOperations

public final class ShuffleOperations extends Object
Automata operations involving shuffling.
  • Method Details

    • 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).