wyautl_old.lang

Class Automata

java.lang.Object

wyautl_old.lang.Automata

public final class Automata
extends Object

This class provides various algorithms for manipulating automata. In particular, the following main algorithms are provided:

• Extraction. This is used to extract one automaton out of another.
• Minimisation. This is used to eliminate equivalent states within an automaton.
• Canonicalisation. This is used to convert an automaton into a canonical form.

Author:

David J. Pearce

Constructor Summary

Constructors

Constructor and Description
Automata()

Method Summary

Modifier and Type	Method and Description
static Automaton	extract(Automaton automaton, int root) Traverse the automaton rooted at the given state and recursively extract all reachable states to produce a (potentially smaller) automaton.
static void	extractOnto(int index, Automaton automaton, ArrayList<Automaton.State> newNodes)
static boolean	isConcrete(Automaton automaton) Check whether or not an automaton is "concrete".
static Automaton	minimise(Automaton automaton) This method minimises an automaton by removing equivalent states.
static Automaton.State	remap(Automaton.State node, int[] rmap) The remap method takes a node, and mapping from vertices in the old space to the those in the new space.

Methods inherited from class java.lang.Object

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

Constructor Detail

Automata

public Automata()

Method Detail

isConcrete

public static boolean isConcrete(Automaton automaton)

Check whether or not an automaton is "concrete". A concrete automaton cannot have recursive links or non-deterministic states.'

extract

public static Automaton extract(Automaton automaton,
                                int root)

Traverse the automaton rooted at the given state and recursively extract all reachable states to produce a (potentially smaller) automaton.

NOTE: one additional use-case for this method is to effectively "garbage collect" states in the automaton. That is, if you extract from the root of any automaton, you'll get an automaton consisting only of those nodes reachable from the root --- but, no others. Therefore, unreachable nodes (which can arise as a result of other automaton operations) are lost.

Parameters:

automaton - --- automaton to extract from

root - --- state in automaton to begin extraction from

Returns:

--- extracted automaton.

extractOnto

public static void extractOnto(int index,
                               Automaton automaton,
                               ArrayList<Automaton.State> newNodes)

minimise

public static final Automaton minimise(Automaton automaton)

This method minimises an automaton by removing equivalent states. Two states s1 and s2 are considered equivalent under the following conditions:

• They are both leaf nodes of the same kind with identical supplementary data.
• They are nodes of the same (sequential) kind whose children at each position are equivalent
• They are nodes of the same (non-sequential) kind where for each child in one, there is an equivalent child in the other and vice-versa.

Parameters:

automaton - --- automaton to minimise

Returns:

--- minimised automaton

remap

public static Automaton.State remap(Automaton.State node,
                                    int[] rmap)

The remap method takes a node, and mapping from vertices in the old space to the those in the new space. It then applies this mapping, so that the node now refers to vertices in the new space. Or, in other words, it transposes the node into the new space.

Parameters:

node - --- node to be transposed.

rmap - --- mapping from integers in old space to those in new space.