Package org.apache.lucene.util.automaton

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

    • Constructor Detail

      • AutomatonTestUtil

        public AutomatonTestUtil()

    • Method Detail

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