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

NFAs.accessibleStates(NFA, Collection), NFAs.coaccessibleStates(NFA, Collection)

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:

NFAs.accessibleStates(NFA, Collection), NFAs.coaccessibleStates(NFA, Collection)

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)

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.

Type Parameters:

I - input symbol type

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

Type Parameters:

I - input symbol type

S - state type

A - automaton type

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:

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