dk.brics.automaton
Class ShuffleOperations

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

public final class ShuffleOperations
extends java.lang.Object

Automata operations involving shuffling.


Method Summary
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 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 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 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).



Copyright © 2001-2011 Anders Møller.