Package org.apache.lucene.tests.util.automaton

Class AutomatonTestUtil

java.lang.Object

org.apache.lucene.tests.util.automaton.AutomatonTestUtil

public class AutomatonTestUtil
extends Object

Utilities for testing automata.

Capable of generating random regular expressions, and automata, and also provides a number of very basic unoptimized implementations (*slow) for testing.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	AutomatonTestUtil.RandomAcceptedStrings	Lets you retrieve random strings accepted by an Automaton.

Field Summary

Fields

Modifier and Type	Field	Description
static final int	DEFAULT_MAX_DETERMINIZED_STATES	Default maximum number of states that Operations.determinize(org.apache.lucene.util.automaton.Automaton, int) should create.

Constructor Summary

Constructors

Constructor	Description
AutomatonTestUtil()

Method Summary

Modifier and Type	Method	Description
static void	assertNoDetachedStates(Automaton a)	Checks that an automaton has no detached states that are unreachable from the initial state.
static Automaton	determinizeSimple(Automaton a)	Simple, original brics implementation of determinize()
static Automaton	determinizeSimple(Automaton a, Set<Integer> initialset)	Simple, original brics implementation of determinize() Determinizes the given automaton using the given set of initial states.
static Set<IntsRef>	getFiniteStringsRecursive(Automaton a, int limit)	Simple, original implementation of getFiniteStrings.
static boolean	isDeterministicSlow(Automaton a)	Returns true if the automaton is deterministic.
static boolean	isFiniteSlow(Automaton a)	Returns true if the language of this automaton is finite.
static Automaton	minimizeSimple(Automaton a)	Simple, original brics implementation of Brzozowski minimize()
static Automaton	randomAutomaton(Random random)	return a random NFA/DFA for testing
static String	randomRegexp(Random r)	Returns random string, including full unicode range.

Methods inherited from class java.lang.Object

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

Field Details

DEFAULT_MAX_DETERMINIZED_STATES

public static final int DEFAULT_MAX_DETERMINIZED_STATES

Default maximum number of states that Operations.determinize(org.apache.lucene.util.automaton.Automaton, int) should create.

See Also:

• Constant Field Values

Constructor Details

AutomatonTestUtil

public AutomatonTestUtil()

Method Details

randomRegexp

public static String randomRegexp(Random r)

Returns random string, including full unicode range.

randomAutomaton

public static Automaton randomAutomaton(Random random)

return a random NFA/DFA for testing

minimizeSimple

public static Automaton minimizeSimple(Automaton a)

Simple, original brics implementation of Brzozowski minimize()

determinizeSimple

public static Automaton determinizeSimple(Automaton a)

Simple, original brics implementation of determinize()

determinizeSimple

public static Automaton determinizeSimple(Automaton a,
 Set<Integer> initialset)

Simple, original brics implementation of determinize() Determinizes the given automaton using the given set of initial states.

getFiniteStringsRecursive

public static Set<IntsRef> getFiniteStringsRecursive(Automaton a,
 int limit)

Simple, original implementation of getFiniteStrings.

Returns the set of accepted strings, assuming that at most limit strings are accepted. If more than limit strings are accepted, the first limit strings found are returned. If limit<0, then the limit is infinite.

This implementation is recursive: it uses one stack frame for each digit in the returned strings (ie, max is the max length returned string).

isFiniteSlow

public static boolean isFiniteSlow(Automaton a)

Returns true if the language of this automaton is finite.

WARNING: this method is slow, it will blow up if the automaton is large. this is only used to test the correctness of our faster implementation.

assertNoDetachedStates

public static void assertNoDetachedStates(Automaton a)

Checks that an automaton has no detached states that are unreachable from the initial state.

isDeterministicSlow

public static boolean isDeterministicSlow(Automaton a)

Returns true if the automaton is deterministic.