dk.brics.automaton

## Class BasicOperations

- java.lang.Object
- - dk.brics.automaton.BasicOperations

-     public final class BasicOperations
      extends java.lang.Object

  Basic automata operations.

- - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `static void` | `addEpsilons(Automaton a, java.util.Collection<StatePair> pairs)` Adds epsilon transitions to the given automaton.
    `static Automaton` | `complement(Automaton a)` Returns a (deterministic) automaton that accepts the complement of the language of the given automaton.
    `static Automaton` | `concatenate(Automaton a1, Automaton a2)` Returns an automaton that accepts the concatenation of the languages of the given automata.
    `static Automaton` | `concatenate(java.util.List<Automaton> l)` Returns an automaton that accepts the concatenation of the languages of the given automata.
    `static void` | `determinize(Automaton a)` Determinizes the given automaton.
    `static java.lang.String` | `getShortestExample(Automaton a, boolean accepted)` Returns a shortest accepted/rejected string.
    `static Automaton` | `intersection(Automaton a1, Automaton a2)` Returns an automaton that accepts the intersection of the languages of the given automata.
    `static boolean` | `isEmpty(Automaton a)` Returns true if the given automaton accepts no strings.
    `static boolean` | `isEmptyString(Automaton a)` Returns true if the given automaton accepts the empty string and nothing else.
    `static boolean` | `isTotal(Automaton a)` Returns true if the given automaton accepts all strings.
    `static Automaton` | `minus(Automaton a1, Automaton a2)` Returns a (deterministic) automaton that accepts the intersection of the language of `a1` and the complement of the language of `a2`.
    `static Automaton` | `optional(Automaton a)` Returns an automaton that accepts the union of the empty string and the language of the given automaton.
    `static Automaton` | `repeat(Automaton a)` Returns an automaton that accepts the Kleene star (zero or more concatenated repetitions) of the language of the given automaton.
    `static Automaton` | `repeat(Automaton a, int min)` Returns an automaton that accepts `min` or more concatenated repetitions of the language of the given automaton.
    `static Automaton` | `repeat(Automaton a, int min, int max)` Returns an automaton that accepts between `min` and `max` (including both) concatenated repetitions of the language of the given automaton.
    `static boolean` | `run(Automaton a, java.lang.String s)` Returns true if the given string is accepted by the automaton.
    `static boolean` | `subsetOf(Automaton a1, Automaton a2)` Returns true if the language of `a1` is a subset of the language of `a2`.
    `static Automaton` | `union(Automaton a1, Automaton a2)` Returns an automaton that accepts the union of the languages of the given automata.
    `static Automaton` | `union(java.util.Collection<Automaton> l)` Returns an automaton that accepts the union of the languages of the given automata.

    - ### Methods inherited from class java.lang.Object

      `equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Method Detail

    - #### concatenate

          public static Automaton concatenate(Automaton a1,
                              Automaton a2)

      Returns an automaton that accepts the concatenation of the languages of the given automata.

      Complexity: linear in number of states.

    - #### concatenate

          public static Automaton concatenate(java.util.List<Automaton> l)

      Returns an automaton that accepts the concatenation of the languages of the given automata.

      Complexity: linear in total number of states.

    - #### optional

          public static Automaton optional(Automaton a)

      Returns an automaton that accepts the union of the empty string and the language of the given automaton.

      Complexity: linear in number of states.

    - #### repeat

          public static Automaton repeat(Automaton a)

      Returns an automaton that accepts the Kleene star (zero or more concatenated repetitions) of the language of the given automaton. Never modifies the input automaton language.

      Complexity: linear in number of states.

    - #### repeat

          public static Automaton repeat(Automaton a,
                         int min)

      Returns an automaton that accepts `min` or more concatenated repetitions of the language of the given automaton.

      Complexity: linear in number of states and in `min`.

    - #### repeat

          public static Automaton repeat(Automaton a,
                         int min,
                         int max)

      Returns an automaton that accepts between `min` and `max` (including both) concatenated repetitions of the language of the given automaton.

      Complexity: linear in number of states and in `min` and `max`.

    - #### complement

          public static Automaton complement(Automaton a)

      Returns a (deterministic) automaton that accepts the complement of the language of the given automaton.

      Complexity: linear in number of states (if already deterministic).

    - #### minus

          public static Automaton minus(Automaton a1,
                        Automaton a2)

      Returns a (deterministic) automaton that accepts the intersection of the language of `a1` and the complement of the language of `a2`. As a side-effect, the automata may be determinized, if not already deterministic.

      Complexity: quadratic in number of states (if already deterministic).

    - #### intersection

          public static Automaton intersection(Automaton a1,
                               Automaton a2)

      Returns an automaton that accepts the intersection of the languages of the given automata. Never modifies the input automata languages.

      Complexity: quadratic in number of 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`. As a side-effect, `a2` is determinized if not already marked as deterministic.

      Complexity: quadratic in number of states.

    - #### union

          public static Automaton union(Automaton a1,
                        Automaton a2)

      Returns an automaton that accepts the union of the languages of the given automata.

      Complexity: linear in number of states.

    - #### union

          public static Automaton union(java.util.Collection<Automaton> l)

      Returns an automaton that accepts the union of the languages of the given automata.

      Complexity: linear in number of states.

    - #### determinize

          public static void determinize(Automaton a)

      Determinizes the given automaton.

      Complexity: exponential in number of states.

    - #### addEpsilons

          public static void addEpsilons(Automaton a,
                         java.util.Collection<StatePair> pairs)

      Adds epsilon transitions to the given automaton. This method adds extra character interval transitions that are equivalent to the given set of epsilon transitions.
      Parameters:
        `pairs` - collection of `StatePair` objects representing pairs of source/destination states where epsilon transitions should be added

    - #### isEmptyString

          public static boolean isEmptyString(Automaton a)

      Returns true if the given automaton accepts the empty string and nothing else.

    - #### isEmpty

          public static boolean isEmpty(Automaton a)

      Returns true if the given automaton accepts no strings.

    - #### isTotal

          public static boolean isTotal(Automaton a)

      Returns true if the given automaton accepts all strings.

    - #### getShortestExample

          public static java.lang.String getShortestExample(Automaton a,
                                            boolean accepted)

      Returns a shortest accepted/rejected string. If more than one shortest string is found, the lexicographically first of the shortest strings is returned.
      Parameters:
        `accepted` - if true, look for accepted strings; otherwise, look for rejected strings
      Returns:
        the string, null if none found

    - #### run

          public static boolean run(Automaton a,
                    java.lang.String s)

      Returns true if the given string is accepted by the automaton.

      Complexity: linear in the length of the string.

      Note: for full performance, use the `RunAutomaton` class.