dk.brics.grammar.operations
Class AutomataOperations

java.lang.Object
  dk.brics.grammar.operations.AutomataOperations

public class AutomataOperations
extends Object

Special automata operations used in RegularApproximation.

Method Summary

static Automaton	expandAlphabet(Automaton a, char n) Expands the alphabet of the given alphabet by replacing each transition with two consecutive transitions.
static Automaton	getOverlap(Automaton a1, Automaton a2) Constructs overlap automaton with expanded alphabet for the two given automata.
static HorizontalOverlapString	getOverlapString(Automaton overlap) Finds a shortest example overlap string.

Methods inherited from class java.lang.Object

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

Method Detail

expandAlphabet

public static Automaton expandAlphabet(Automaton a,
                                       char n)

Expands the alphabet of the given alphabet by replacing each transition with two consecutive transitions. A transition from p to q with label c becomes two transitions (n,c) from p to q via a fresh state.

Parameters:

a - input automaton (unmodified)

n - label for new transitions

Returns:

new automaton

getOverlap

public static Automaton getOverlap(Automaton a1,
                                   Automaton a2)

Constructs overlap automaton with expanded alphabet for the two given automata. All accepted strings contain two (\u0001,\u0000) markers, splitting the string into three parts.

Parameters:

a1 - left automaton

a2 - right automaton

Returns:

overlap automaton

getOverlapString

public static HorizontalOverlapString getOverlapString(Automaton overlap)

Finds a shortest example overlap string.

Parameters:

overlap - overlap automaton

Returns:

overlap string, null if no overlap