Class SpecialOperations


  • public final class SpecialOperations
    extends java.lang.Object
    Special automata operations.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private SpecialOperations()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      private static void acceptToAccept​(Automaton a)  
      private static void addSetTransitions​(State s, java.lang.String set, State p)  
      static Automaton compress​(Automaton a, java.lang.String set, char c)
      Returns an automaton that accepts the compressed language of the given automaton.
      (package private) static int findIndex​(char c, char[] points)
      Finds the largest entry whose value is less than or equal to c, or 0 if there is no such entry.
      static java.lang.String getCommonPrefix​(Automaton a)
      Returns the longest string that is a prefix of all accepted strings and visits each state at most once.
      static java.util.Set<java.lang.String> getFiniteStrings​(Automaton a)
      Returns the set of accepted strings, assuming this automaton has a finite language.
      static java.util.Set<java.lang.String> getFiniteStrings​(Automaton a, int limit)
      Returns the set of accepted strings, assuming that at most limit strings are accepted.
      private static boolean getFiniteStrings​(State s, java.util.HashSet<State> pathstates, java.util.HashSet<java.lang.String> strings, java.lang.StringBuilder path, int limit)
      Returns the strings that can be produced from the given state, or false if more than limit strings are found.
      static java.util.Set<java.lang.String> getStrings​(Automaton a, int length)
      Returns the set of accepted strings of the given length.
      private static void getStrings​(State s, java.util.Set<java.lang.String> strings, java.lang.StringBuilder path, int length)  
      static Automaton hexCases​(Automaton a)
      Constructs automaton that accepts the same strings as the given automaton but ignores upper/lower case of A-F.
      static Automaton homomorph​(Automaton a, char[] source, char[] dest)
      Returns an automaton accepting the homomorphic image of the given automaton using the given function.
      static boolean isFinite​(Automaton a)
      Returns true if the language of this automaton is finite.
      private static boolean isFinite​(State s, java.util.HashSet<State> path, java.util.HashSet<State> visited)
      Checks whether there is a loop containing s.
      static Automaton overlap​(Automaton a1, Automaton a2)
      Returns an automaton that accepts the overlap of strings that in more than one way can be split into a left part being accepted by a1 and a right part being accepted by a2.
      static void prefixClose​(Automaton a)
      Prefix closes the given automaton.
      static Automaton projectChars​(Automaton a, java.util.Set<java.lang.Character> chars)
      Returns an automaton with projected alphabet.
      static Automaton replaceWhitespace​(Automaton a)
      Constructs automaton that accepts 0x20, 0x9, 0xa, and 0xd in place of each 0x20 transition in the given automaton.
      static java.util.Set<State> reverse​(Automaton a)
      Reverses the language of the given (non-singleton) automaton while returning the set of new initial states.
      static Automaton singleChars​(Automaton a)
      Returns an automaton that accepts the single chars that occur in strings that are accepted by the given automaton.
      static Automaton subst​(Automaton a, char c, java.lang.String s)
      Returns an automaton where all transitions of the given char are replaced by a string.
      static Automaton subst​(Automaton a, java.util.Map<java.lang.Character,​java.util.Set<java.lang.Character>> map)
      Returns an automaton where all transition labels have been substituted.
      static Automaton trim​(Automaton a, java.lang.String set, char c)
      Returns an automaton that accepts the trimmed language of the given automaton.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • SpecialOperations

        private SpecialOperations()
    • Method Detail

      • reverse

        public static java.util.Set<State> reverse​(Automaton a)
        Reverses the language of the given (non-singleton) automaton while returning the set of new initial states.
      • overlap

        public static Automaton overlap​(Automaton a1,
                                        Automaton a2)
        Returns an automaton that accepts the overlap of strings that in more than one way can be split into a left part being accepted by a1 and a right part being accepted by a2.
      • acceptToAccept

        private static void acceptToAccept​(Automaton a)
      • singleChars

        public static Automaton singleChars​(Automaton a)
        Returns an automaton that accepts the single chars that occur in strings that are accepted by the given automaton. Never modifies the input automaton.
      • trim

        public static Automaton trim​(Automaton a,
                                     java.lang.String set,
                                     char c)
        Returns an automaton that accepts the trimmed language of the given automaton. The resulting automaton is constructed as follows: 1) Whenever a c character is allowed in the original automaton, one or more set characters are allowed in the new automaton. 2) The automaton is prefixed and postfixed with any number of set characters.
        Parameters:
        set - set of characters to be trimmed
        c - canonical trim character (assumed to be in set)
      • addSetTransitions

        private static void addSetTransitions​(State s,
                                              java.lang.String set,
                                              State p)
      • compress

        public static Automaton compress​(Automaton a,
                                         java.lang.String set,
                                         char c)
        Returns an automaton that accepts the compressed language of the given automaton. Whenever a c character is allowed in the original automaton, one or more set characters are allowed in the new automaton.
        Parameters:
        set - set of characters to be compressed
        c - canonical compress character (assumed to be in set)
      • subst

        public static Automaton subst​(Automaton a,
                                      java.util.Map<java.lang.Character,​java.util.Set<java.lang.Character>> map)
        Returns an automaton where all transition labels have been substituted.

        Each transition labeled c is changed to a set of transitions, one for each character in map(c). If map(c) is null, then the transition is unchanged.

        Parameters:
        map - map from characters to sets of characters (where characters are Character objects)
      • findIndex

        static int findIndex​(char c,
                             char[] points)
        Finds the largest entry whose value is less than or equal to c, or 0 if there is no such entry.
      • subst

        public static Automaton subst​(Automaton a,
                                      char c,
                                      java.lang.String s)
        Returns an automaton where all transitions of the given char are replaced by a string.
        Parameters:
        c - char
        s - string
        Returns:
        new automaton
      • homomorph

        public static Automaton homomorph​(Automaton a,
                                          char[] source,
                                          char[] dest)
        Returns an automaton accepting the homomorphic image of the given automaton using the given function.

        This method maps each transition label to a new value. source and dest are assumed to be arrays of same length, and source must be sorted in increasing order and contain no duplicates. source defines the starting points of char intervals, and the corresponding entries in dest define the starting points of corresponding new intervals.

      • projectChars

        public static Automaton projectChars​(Automaton a,
                                             java.util.Set<java.lang.Character> chars)
        Returns an automaton with projected alphabet. The new automaton accepts all strings that are projections of strings accepted by the given automaton onto the given characters (represented by Character). If null is in the set, it abbreviates the intervals u0000-uDFFF and uF900-uFFFF (i.e., the non-private code points). It is assumed that all other characters from chars are in the interval uE000-uF8FF.
      • isFinite

        public static boolean isFinite​(Automaton a)
        Returns true if the language of this automaton is finite.
      • isFinite

        private static boolean isFinite​(State s,
                                        java.util.HashSet<State> path,
                                        java.util.HashSet<State> visited)
        Checks whether there is a loop containing s. (This is sufficient since there are never transitions to dead states.)
      • getStrings

        public static java.util.Set<java.lang.String> getStrings​(Automaton a,
                                                                 int length)
        Returns the set of accepted strings of the given length.
      • getStrings

        private static void getStrings​(State s,
                                       java.util.Set<java.lang.String> strings,
                                       java.lang.StringBuilder path,
                                       int length)
      • getFiniteStrings

        public static java.util.Set<java.lang.String> getFiniteStrings​(Automaton a)
        Returns the set of accepted strings, assuming this automaton has a finite language. If the language is not finite, null is returned.
      • getFiniteStrings

        public static java.util.Set<java.lang.String> getFiniteStrings​(Automaton a,
                                                                       int limit)
        Returns the set of accepted strings, assuming that at most limit strings are accepted. If more than limit strings are accepted, null is returned. If limit<0, then this methods works like getFiniteStrings(Automaton).
      • getFiniteStrings

        private static boolean getFiniteStrings​(State s,
                                                java.util.HashSet<State> pathstates,
                                                java.util.HashSet<java.lang.String> strings,
                                                java.lang.StringBuilder path,
                                                int limit)
        Returns the strings that can be produced from the given state, or false if more than limit strings are found. limit<0 means "infinite".
      • getCommonPrefix

        public static java.lang.String getCommonPrefix​(Automaton a)
        Returns the longest string that is a prefix of all accepted strings and visits each state at most once.
        Returns:
        common prefix
      • prefixClose

        public static void prefixClose​(Automaton a)
        Prefix closes the given automaton.
      • hexCases

        public static Automaton hexCases​(Automaton a)
        Constructs automaton that accepts the same strings as the given automaton but ignores upper/lower case of A-F.
        Parameters:
        a - automaton
        Returns:
        automaton
      • replaceWhitespace

        public static Automaton replaceWhitespace​(Automaton a)
        Constructs automaton that accepts 0x20, 0x9, 0xa, and 0xd in place of each 0x20 transition in the given automaton.
        Parameters:
        a - automaton
        Returns:
        automaton