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

Class AutomatonTestUtil

java.lang.Object

org.junit.Assert

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

public class AutomatonTestUtil
extends Assert

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.
static final int	MAX_RECURSION_LEVEL	Maximum level of recursion allowed in recursive operations.

Constructor Summary

Constructors

Constructor	Description
AutomatonTestUtil()

Method Summary

Modifier and Type	Method	Description
static void	assertCleanDFA(Automaton automaton)	Asserts that an automaton is a DFA with no dead states
static void	assertCleanNFA(Automaton automaton)	Asserts that an automaton has no dead states
static void	assertMinimalDFA(Automaton automaton)	Asserts that an automaton is a minimal DFA.
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	isFinite(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.
static Automaton	reverseOriginal(Automaton a, Set<Integer> initialStates)	Original brics implementation of reverse().
static boolean	sameLanguage(Automaton a1, Automaton a2)	Returns true if these two automata accept exactly the same language.
static boolean	subsetOf(Automaton a1, Automaton a2)	Returns true if the language of a1 is a subset of the language of a2.

Methods inherited from class org.junit.Assert

assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertArrayEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotEquals, assertNotEquals, assertNotEquals, assertNotEquals, assertNotEquals, assertNotEquals, assertNotEquals, assertNotEquals, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertThat, assertThat, assertThrows, assertThrows, assertTrue, assertTrue, fail, fail

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

MAX_RECURSION_LEVEL

public static final int MAX_RECURSION_LEVEL

Maximum level of recursion allowed in recursive operations.

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

reverseOriginal

public static Automaton reverseOriginal(Automaton a,
 Set<Integer> initialStates)

Original brics implementation of reverse(). It tries to satisfy multiple use-cases by populating a set of initial states too.

minimizeSimple

public static Automaton minimizeSimple(Automaton a)

Simple, original brics implementation of Brzozowski minimize()

assertMinimalDFA

public static void assertMinimalDFA(Automaton automaton)

Asserts that an automaton is a minimal DFA.

assertCleanDFA

public static void assertCleanDFA(Automaton automaton)

Asserts that an automaton is a DFA with no dead states

assertCleanNFA

public static void assertCleanNFA(Automaton automaton)

Asserts that an automaton has no dead states

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

isFinite

public static boolean isFinite(Automaton a)

Returns true if the language of this automaton is finite. The automaton must not have any dead states.

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.

sameLanguage

public static boolean sameLanguage(Automaton a1,
 Automaton a2)

Returns true if these two automata accept exactly the same language. This is a costly computation! Both automata must be determinized and have no dead states!

subsetOf

public static boolean subsetOf(Automaton a1,
 Automaton a2)

Returns true if the language of a1 is a subset of the language of a2. Both automata must be determinized and must have no dead states.

Complexity: quadratic in number of states.