dk.brics.automaton

Class ShuffleOperations

public final class ShuffleOperations extends Object

Automata operations involving shuffling.
Method Summary
static Automatonshuffle(Automaton a1, Automaton a2)
Returns an automaton that accepts the shuffle (interleaving) of the languages of the given automata.
static StringshuffleSubsetOf(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.

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

Copyright © 2001-2009 Anders Møller.