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 DFA, 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 DFA, 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.
static <I> CompactDFA<I>	combine(DFA<?,I> dfa1, DFA<?,I> dfa2, Alphabet<I> inputAlphabet, AcceptanceCombiner combiner)	Most general way of combining two DFAs.
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 DFA, 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 DFA, 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 DFA, 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 DFA, 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 <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> CompactDFA<I>	minimize(A dfa)	Minimizes the given DFA.
static <I> CompactDFA<I>	minimize(DFA<?,I> dfa, Alphabet<I> alphabet)	Minimizes the given DFA over the given alphabet.
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 DFA, 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 DFA, and returns the result as a new 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 DFA, 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 DFA, 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 Detail

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

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

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 DFA, and returns the result as a new DFA.

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 DFA, and stores the result in a given mutable DFA.

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 DFA, and returns the result as a new DFA.

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 DFA, and stores the result in a given mutable DFA.

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 DFA, and returns the result as a new DFA.

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 DFA, and stores the result in a given mutable DFA.

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 DFA, and returns the result as a new DFA.

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 DFA, and stores the result in a given mutable DFA.

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 DFA, and returns the result as a new DFA.

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 DFA, and stores the result in a given mutable DFA.

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

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

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

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)

minimize

public static <I> CompactDFA<I> minimize(DFA<?,I> dfa,
                                         Alphabet<I> alphabet)

Minimizes the given DFA over the given alphabet. This method does not modify the given DFA, but returns the minimized version as a new instance.

Note: the DFA must be completely specified.

Parameters:

dfa - the DFA to be minimized

alphabet - the input alphabet to consider for minimization (this will also be the input alphabet of the resulting automaton)

Returns:

a minimized version of the specified DFA

minimize

public static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> CompactDFA<I> minimize(A dfa)

Minimizes the given DFA. This method does not modify the given DFA, but returns the minimized version as a new instance.

Note: the DFA must be completely specified

Parameters:

dfa - the DFA to be minimized

Returns:

a minimized version of the specified DFA

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:

S - the type of state

I - the type of input

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 - the state type.

Parameters:

dfa - the DFA to check.

Returns:

whether the given DFA accepts the empty language.