Module net.automatalib.util
Package net.automatalib.util.automaton.fsa

Class DFAs

java.lang.Object
net.automatalib.util.automaton.fsa.DFAs
public final class DFAs extends Object
Operations on DFAs.

Note that the methods provided by this class do not modify their input arguments. Such methods are instead provided by the MutableDFAs class. Furthermore, results are copied into new datastructures. For read-only views you may use the more generic Acceptors factory.

  • Method Summary

    Modifier and Type
    Method
    Description
    static <S> boolean
    acceptsEmptyLanguage(DFA<S,?> dfa)
    Computes whether the given DFA accepts the empty language.
    static <I, S, A extends MutableDFA<S, I>>
    A
    and(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
    Calculates the conjunction ("and") of two DFAs via product construction and stores the result in a given mutable DFA.
    static <I> CompactDFA<I>
    and(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
    Calculates the conjunction ("and") of two DFAs via product construction and returns the result as a new DFA.
    static <I, S, A extends MutableDFA<S, I>>
    A
    combine(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out, AcceptanceCombiner combiner)
    Most general way of combining two DFAs via product construction.
    static <I> CompactDFA<I>
    combine(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet, AcceptanceCombiner combiner)
    Most general way of combining two DFAs via product construction.
    static <I, S, A extends MutableDFA<S, I>>
    A
    complement(DFA<?,I> dfa, Collection<? extends I> inputs, A out)
    Calculates the complement (negation) of a DFA, and stores the result in a given mutable DFA.
    static <I> CompactDFA<I>
    complement(DFA<?,I> dfa, Alphabet<I> inputAlphabet)
    Calculates the complement (negation) of a DFA and returns the result as a new DFA.
    static <I, S, A extends MutableDFA<S, I>>
    A
    complete(DFA<?,I> dfa, Collection<? extends I> inputs, A out)
     
    static <I> CompactDFA<I>
    complete(DFA<?,I> dfa, Alphabet<I> inputs)
     
    static <I, S, A extends MutableDFA<S, I>>
    A
    equiv(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
    Calculates the equivalence ("<=>") of two DFAs via product construction and stores the result in a given mutable DFA.
    static <I> CompactDFA<I>
    equiv(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
    Calculates the equivalence ("<=>") of two DFAs via product construction and returns the result as a new DFA.
    static <I, S, A extends MutableDFA<S, I>>
    A
    impl(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
    Calculates the implication ("=>") of two DFAs via product construction and stores the result in a given mutable DFA.
    static <I> CompactDFA<I>
    impl(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
    Calculates the implication ("=>") of two DFAs via product construction and returns the result as a new DFA.
    static <S, I> boolean
    isPrefixClosed(DFA<S,I> dfa, Collection<I> inputs)
    Computes whether the language of the given DFA is prefix-closed.
    static <I, S, A extends MutableDFA<S, I>>
    A
    or(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
    Calculates the disjunction ("or") of two DFAs via product construction and stores the result in a given mutable DFA.
    static <I> CompactDFA<I>
    or(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
    Calculates the disjunction ("or") of two DFAs via product construction and returns the result as a new DFA.
    static <I> CompactDFA<I>
    trim(DFA<?,I> dfa, Alphabet<I> inputAlphabet)
    Creates a trim DFA from the given input DFA.
    static <SI, I, SO, A extends MutableDFA<SO, I>>
    A
    trim(DFA<SI,I> dfa, Collection<? extends I> inputs, A out)
    Creates a trim DFA from the given input DFA and writes it to the given output DFA.
    static <I, S, A extends MutableDFA<S, I>>
    A
    xor(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
    Calculates the exclusive-or ("xor") of two DFAs via product construction and stores the result in a given mutable DFA.
    static <I> CompactDFA<I>
    xor(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
    Calculates the exclusive-or ("xor") of two DFAs via product construction and returns the result as a new DFA.

    Methods inherited from class java.lang.Object

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

  • Method Details

    • combine

      public static <I> CompactDFA<I> combine(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet, AcceptanceCombiner combiner)
      Most general way of combining two DFAs via product construction. The behavior is the same as of the above combine(DFA, DFA, Collection, MutableDFA, AcceptanceCombiner), but the result automaton is automatically created as a CompactDFA.
      Type Parameters:
      I - input symbol type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputAlphabet - the input alphabet
      combiner - combination method for acceptance values
      Returns:
      a new DFA representing the combination of the specified DFA

    • combine

      public static <I, S, A extends MutableDFA<S, I>> A combine(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out, AcceptanceCombiner combiner)
      Most general way of combining two DFAs via product construction. The AcceptanceCombiner specified via the combiner parameter specifies how acceptance values of the DFAs will be combined to an acceptance value in the result DFA.
      Type Parameters:
      I - input symbol type
      S - state type
      A - automaton type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputs - the input symbols to consider
      out - the mutable DFA for storing the result
      combiner - combination method for acceptance values
      Returns:
      out, for convenience

    • and

      public static <I> CompactDFA<I> and(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
      Calculates the conjunction ("and") of two DFAs via product construction and returns the result as a new DFA.
      Type Parameters:
      I - input symbol type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputAlphabet - the input alphabet
      Returns:
      a new DFA representing the conjunction of the specified DFA

    • and

      public static <I, S, A extends MutableDFA<S, I>> A and(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
      Calculates the conjunction ("and") of two DFAs via product construction and stores the result in a given mutable DFA.
      Type Parameters:
      I - input symbol type
      S - state type
      A - automaton type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputs - the input symbols to consider
      out - a mutable DFA for storing the result
      Returns:
      out, for convenience

    • or

      public static <I> CompactDFA<I> or(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
      Calculates the disjunction ("or") of two DFAs via product construction and returns the result as a new DFA.
      Type Parameters:
      I - input symbol type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputAlphabet - the input alphabet
      Returns:
      a new DFA representing the conjunction of the specified DFA

    • or

      public static <I, S, A extends MutableDFA<S, I>> A or(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
      Calculates the disjunction ("or") of two DFAs via product construction and stores the result in a given mutable DFA.
      Type Parameters:
      I - input symbol type
      S - state type
      A - automaton type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputs - the input symbols to consider
      out - a mutable DFA for storing the result
      Returns:
      out, for convenience

    • xor

      public static <I> CompactDFA<I> xor(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
      Calculates the exclusive-or ("xor") of two DFAs via product construction and returns the result as a new DFA.
      Type Parameters:
      I - input symbol type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputAlphabet - the input alphabet
      Returns:
      a new DFA representing the conjunction of the specified DFA

    • xor

      public static <I, S, A extends MutableDFA<S, I>> A xor(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
      Calculates the exclusive-or ("xor") of two DFAs via product construction and stores the result in a given mutable DFA.
      Type Parameters:
      I - input symbol type
      S - state type
      A - automaton type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputs - the input symbols to consider
      out - a mutable DFA for storing the result
      Returns:
      out, for convenience

    • equiv

      public static <I> CompactDFA<I> equiv(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
      Calculates the equivalence ("<=>") of two DFAs via product construction and returns the result as a new DFA.
      Type Parameters:
      I - input symbol type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputAlphabet - the input alphabet
      Returns:
      a new DFA representing the conjunction of the specified DFA

    • equiv

      public static <I, S, A extends MutableDFA<S, I>> A equiv(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
      Calculates the equivalence ("<=>") of two DFAs via product construction and stores the result in a given mutable DFA.
      Type Parameters:
      I - input symbol type
      S - state type
      A - automaton type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputs - the input symbols to consider
      out - a mutable DFA for storing the result
      Returns:
      out, for convenience

    • impl

      public static <I> CompactDFA<I> impl(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet)
      Calculates the implication ("=>") of two DFAs via product construction and returns the result as a new DFA.
      Type Parameters:
      I - input symbol type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputAlphabet - the input alphabet
      Returns:
      a new DFA representing the conjunction of the specified DFA

    • impl

      public static <I, S, A extends MutableDFA<S, I>> A impl(DFA<?,I> dfa1, DFA<?,I> dfa2, Collection<? extends I> inputs, A out)
      Calculates the implication ("=>") of two DFAs via product construction and stores the result in a given mutable DFA.
      Type Parameters:
      I - input symbol type
      S - state type
      A - automaton type
      Parameters:
      dfa1 - the first DFA
      dfa2 - the second DFA
      inputs - the input symbols to consider
      out - a mutable DFA for storing the result
      Returns:
      out, for convenience

    • trim

      public static <I> CompactDFA<I> trim(DFA<?,I> dfa, Alphabet<I> inputAlphabet)
      Creates a trim DFA from the given input DFA. A DFA is trim if all of its states are accessible and co-accessible.
      Type Parameters:
      I - input symbol type
      Parameters:
      dfa - the input DFA
      inputAlphabet - the input alphabet
      Returns:
      the trim DFA
      See Also:

    • trim

      public static <SI, I, SO, A extends MutableDFA<SO, I>> A trim(DFA<SI,I> dfa, Collection<? extends I> inputs, A out)
      Creates a trim DFA from the given input DFA and writes it to the given output DFA. A DFA is trim if all of its states are accessible and co-accessible.
      Type Parameters:
      SI - (input) state type
      I - input symbol type
      SO - (output) state type
      A - (output) automaton type
      Parameters:
      dfa - the input DFA
      inputs - the input symbols to consider
      out - the output NFA
      Returns:
      out for convenience
      See Also:

    • complement

      public static <I> CompactDFA<I> complement(DFA<?,I> dfa, Alphabet<I> inputAlphabet)
      Calculates the complement (negation) of a DFA and returns the result as a new DFA.

      Note that unlike MutableFSA.flipAcceptance(), undefined transitions are treated as leading to a rejecting sink state (and are thus turned into an accepting sink).

      Type Parameters:
      I - input symbol type
      Parameters:
      dfa - the DFA to complement
      inputAlphabet - the input alphabet
      Returns:
      a new DFA representing the complement of the specified DFA

    • complement

      public static <I, S, A extends MutableDFA<S, I>> A complement(DFA<?,I> dfa, Collection<? extends I> inputs, A out)
      Calculates the complement (negation) of a DFA, and stores the result in a given mutable DFA.

      Note that unlike MutableFSA.flipAcceptance(), undefined transitions are treated as leading to a rejecting sink state (and are thus turned into an accepting sink).

      Type Parameters:
      I - input symbol type
      S - state type
      A - automaton type
      Parameters:
      dfa - the DFA to complement
      inputs - the input symbols to consider
      out - a mutable DFA for storing the result
      Returns:
      out, for convenience

    • complete

      public static <I> CompactDFA<I> complete(DFA<?,I> dfa, Alphabet<I> inputs)

    • complete

      public static <I, S, A extends MutableDFA<S, I>> A complete(DFA<?,I> dfa, Collection<? extends I> inputs, A out)

    • isPrefixClosed

      public static <S, I> boolean isPrefixClosed(DFA<S,I> dfa, Collection<I> inputs)
      Computes whether the language of the given DFA is prefix-closed.

      Assumes all states in the given DFA are reachable from the initial state.

      Type Parameters:
      I - input symbol type
      S - state type
      Parameters:
      dfa - the DFA to check
      inputs - the input symbols to consider
      Returns:
      whether the DFA is prefix-closed

    • acceptsEmptyLanguage

      public static <S> boolean acceptsEmptyLanguage(DFA<S,?> dfa)
      Computes whether the given DFA accepts the empty language.

      Assumes all states in the given DFA are reachable from the initial state.

      Type Parameters:
      S - state type
      Parameters:
      dfa - the DFA to check
      Returns:
      whether the given DFA accepts the empty language