12304577693

Committed 12 Dec 2024 08:51PM UTC coverage: 91.182% (+0.4%) from 90.804%

Build # 12304577693

Build Type

push

github

Committed by

web-flow

Commit Message

Overhaul minimization code (#83)

* add valmaris algorithm

* initial PT refactoring

* implement bisimulation via valmari

* add documentation

* cleanups

* add invasive hopcroft methods

* some more universal tests

* performance tweaks

* move OneSEVPAMinimizer

* improve documentation

* cleanup

* wording

* fix javadoc errors

Run Details

564 of 581 new or added lines in 25 files covered. (97.07%)

1 existing line in 1 file now uncovered.

16535 of 18134 relevant lines covered (91.18%)

1.69 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.55

/util/src/main/java/net/automatalib/util/automaton/fsa/DFAs.java

/* Copyright (C) 2013-2024 TU Dortmund University
 * This file is part of AutomataLib, http://www.automatalib.net/.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.automatalib.util.automaton.fsa;

import java.util.Collection;
import java.util.Objects;
import java.util.Set;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.automaton.concept.InputAlphabetHolder;
import net.automatalib.automaton.fsa.DFA;
import net.automatalib.automaton.fsa.MutableDFA;
import net.automatalib.automaton.fsa.NFA;
import net.automatalib.automaton.fsa.impl.CompactDFA;
import net.automatalib.common.util.mapping.MutableMapping;
import net.automatalib.ts.acceptor.DeterministicAcceptorTS;
import net.automatalib.util.automaton.copy.AutomatonCopyMethod;
import net.automatalib.util.automaton.copy.AutomatonLowLevelCopy;
import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;
import net.automatalib.util.ts.acceptor.AcceptanceCombiner;
import net.automatalib.util.ts.acceptor.Acceptors;
import net.automatalib.util.ts.copy.TSCopy;
import net.automatalib.util.ts.traversal.TSTraversal;
import net.automatalib.util.ts.traversal.TSTraversalMethod;

/**
 * Operations on {@link DFA}s.
 * <p>
 * Note that the methods provided by this class do not modify their input arguments. Such methods are instead provided
 * by the {@link MutableDFAs} class. Furthermore, results are copied into new datastructures. For read-only views you
 * may use the more generic {@link Acceptors} factory.
 */
public final class DFAs {

    private DFAs() {
        // prevent instantiation
    }

    /**
     * Most general way of combining two DFAs. The behavior is the same as of the above {@link #combine(DFA, DFA,
     * Collection, MutableDFA, AcceptanceCombiner)}, but the result automaton is automatically created as a {@link
     * CompactDFA}.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputAlphabet
     *         the input alphabet
     * @param combiner
     *         combination method for acceptance values
     * @param <I>
     *         input symbol type
     *
     * @return a new DFA representing the combination of the specified DFA
     */
    public static <I> CompactDFA<I> combine(DFA<?, I> dfa1,
                                            DFA<?, I> dfa2,
                                            Alphabet<I> inputAlphabet,
                                            AcceptanceCombiner combiner) {
        return combine(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet), combiner);
    }

    /**
     * Most general way of combining two DFAs. The {@link AcceptanceCombiner} specified via the {@code combiner}
     * parameter specifies how acceptance values of the DFAs will be combined to an acceptance value in the result DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         the mutable DFA for storing the result
     * @param combiner
     *         combination method for acceptance values
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    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) {
        DeterministicAcceptorTS<?, I> acc = Acceptors.combine(dfa1, dfa2, combiner);

        TSCopy.copy(TSTraversalMethod.DEPTH_FIRST, acc, TSTraversal.NO_LIMIT, inputs, out);
        return out;
    }

    /**
     * Calculates the conjunction ("and") of two DFA, and returns the result as a new DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return a new DFA representing the conjunction of the specified DFA
     */
    public static <I> CompactDFA<I> and(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
        return and(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));
    }

    /**
     * Calculates the conjunction ("and") of two DFA, and stores the result in a given mutable DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable DFA for storing the result
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    public static <I, S, A extends MutableDFA<S, I>> A and(DFA<?, I> dfa1,
                                                           DFA<?, I> dfa2,
                                                           Collection<? extends I> inputs,
                                                           A out) {
        return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.AND);
    }

    /**
     * Calculates the disjunction ("or") of two DFA, and returns the result as a new DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return a new DFA representing the conjunction of the specified DFA
     */
    public static <I> CompactDFA<I> or(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
        return or(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));
    }

    /**
     * Calculates the disjunction ("or") of two DFA, and stores the result in a given mutable DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable DFA for storing the result
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    public static <I, S, A extends MutableDFA<S, I>> A or(DFA<?, I> dfa1,
                                                          DFA<?, I> dfa2,
                                                          Collection<? extends I> inputs,
                                                          A out) {
        return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.OR);
    }

    /**
     * Calculates the exclusive-or ("xor") of two DFA, and returns the result as a new DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return a new DFA representing the conjunction of the specified DFA
     */
    public static <I> CompactDFA<I> xor(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
        return xor(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));
    }

    /**
     * Calculates the exclusive-or ("xor") of two DFA, and stores the result in a given mutable DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable DFA for storing the result
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    public static <I, S, A extends MutableDFA<S, I>> A xor(DFA<?, I> dfa1,
                                                           DFA<?, I> dfa2,
                                                           Collection<? extends I> inputs,
                                                           A out) {
        return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.XOR);
    }

    /**
     * Calculates the equivalence ("&lt;=&gt;") of two DFA, and returns the result as a new DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return a new DFA representing the conjunction of the specified DFA
     */
    public static <I> CompactDFA<I> equiv(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
        return equiv(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));
    }

    /**
     * Calculates the equivalence ("&lt;=&gt;") of two DFA, and stores the result in a given mutable DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable DFA for storing the result
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    public static <I, S, A extends MutableDFA<S, I>> A equiv(DFA<?, I> dfa1,
                                                             DFA<?, I> dfa2,
                                                             Collection<? extends I> inputs,
                                                             A out) {
        return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.EQUIV);
    }

    /**
     * Calculates the implication ("=&gt;") of two DFA, and returns the result as a new DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return a new DFA representing the conjunction of the specified DFA
     */
    public static <I> CompactDFA<I> impl(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
        return impl(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));
    }

    /**
     * Calculates the implication ("=&gt;") of two DFA, and stores the result in a given mutable DFA.
     *
     * @param dfa1
     *         the first DFA
     * @param dfa2
     *         the second DFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable DFA for storing the result
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    public static <I, S, A extends MutableDFA<S, I>> A impl(DFA<?, I> dfa1,
                                                            DFA<?, I> dfa2,
                                                            Collection<? extends I> inputs,
                                                            A out) {
        return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.IMPL);
    }

    /**
     * Creates a trim DFA from the given input DFA. A DFA is trim if all of its states are accessible and
     * co-accessible.
     *
     * @param dfa
     *         the input DFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return the trim DFA
     *
     * @see NFAs#accessibleStates(NFA, Collection)
     * @see NFAs#coaccessibleStates(NFA, Collection)
     */
    public static <I> CompactDFA<I> trim(DFA<?, I> dfa, Alphabet<I> inputAlphabet) {
        return trim(dfa, inputAlphabet, new CompactDFA<>(inputAlphabet));
    }

    /**
     * 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.
     *
     * @param dfa
     *         the input DFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         the output NFA
     * @param <SI>
     *         (input) state type
     * @param <I>
     *         input symbol type
     * @param <SO>
     *         (output) state type
     * @param <A>
     *         (output) automaton type
     *
     * @return {@code out} for convenience
     *
     * @see NFAs#accessibleStates(NFA, Collection)
     * @see NFAs#coaccessibleStates(NFA, Collection)
     */
    public static <SI, I, SO, A extends MutableDFA<SO, I>> A trim(DFA<SI, I> dfa,
                                                                  Collection<? extends I> inputs,
                                                                  A out) {
        final MutableMapping<SI, SO> mapping = dfa.createStaticStateMapping();
        final SI init = dfa.getInitialState();

        final Set<SI> states = NFAs.accessibleStates(dfa, inputs);
        states.retainAll(NFAs.coaccessibleStates(dfa, inputs));

        for (SI s : states) {
            final SO so = out.addState(dfa.isAccepting(s));
            out.setInitial(so, Objects.equals(init, s));
            mapping.put(s, so);
        }

        for (SI s : states) {
            for (I i : inputs) {
                final SI t = dfa.getSuccessor(s, i);
                if (states.contains(t)) {
                    out.addTransition(mapping.get(s), i, mapping.get(t));
                }
            }
        }

        return out;
    }

    /**
     * Calculates the complement (negation) of a DFA, and returns the result as a new DFA.
     * <p>
     * Note that unlike {@link MutableDFA#flipAcceptance()}, undefined transitions are treated as leading to a rejecting
     * sink state (and are thus turned into an accepting sink).
     *
     * @param dfa
     *         the DFA to complement
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return a new DFA representing the complement of the specified DFA
     */
    public static <I> CompactDFA<I> complement(DFA<?, I> dfa, Alphabet<I> inputAlphabet) {
        return complement(dfa, inputAlphabet, new CompactDFA<>(inputAlphabet));
    }

    /**
     * Calculates the complement (negation) of a DFA, and stores the result in a given mutable DFA.
     * <p>
     * Note that unlike {@link MutableDFA#flipAcceptance()}, undefined transitions are treated as leading to a rejecting
     * sink state (and are thus turned into an accepting sink).
     *
     * @param dfa
     *         the DFA to complement
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable DFA for storing the result
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    public static <I, S, A extends MutableDFA<S, I>> A complement(DFA<?, I> dfa,
                                                                  Collection<? extends I> inputs,
                                                                  A out) {
        AutomatonLowLevelCopy.copy(AutomatonCopyMethod.STATE_BY_STATE,
                                   dfa,
                                   inputs,
                                   out,
                                   b -> b == null || !b,
                                   t -> null);
        MutableDFAs.complete(out, inputs, false, true);
        return out;
    }

    public static <I> CompactDFA<I> complete(DFA<?, I> dfa, Alphabet<I> inputs) {
        return complete(dfa, inputs, new CompactDFA<>(inputs));
    }

    public static <I, S, A extends MutableDFA<S, I>> A complete(DFA<?, I> dfa, Collection<? extends I> inputs, A out) {
        AutomatonLowLevelCopy.copy(AutomatonCopyMethod.DFS, dfa, inputs, out);
        MutableDFAs.complete(out, inputs, true);
        return out;
    }

    /**
     * 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.
     * <p>
     * <b>Note:</b> the DFA must be completely specified.
     *
     * @param dfa
     *         the DFA to be minimized
     * @param alphabet
     *         the input alphabet to consider for minimization (this will also be the input alphabet of the resulting
     *         automaton)
     * @param <I>
     *         input symbol type
     *
     * @return a minimized version of the specified DFA
     */
    public static <I> CompactDFA<I> minimize(DFA<?, I> dfa, Alphabet<I> alphabet) {
        return HopcroftMinimizer.minimizeDFA(dfa, alphabet);
    }

    /**
     * Minimizes the given DFA. This method does not modify the given DFA, but returns the minimized version as a new
     * instance.
     * <p>
     * <b>Note:</b> the DFA must be completely specified
     *
     * @param dfa
     *         the DFA to be minimized
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     * @param <A>
     *         automaton type
     *
     * @return a minimized version of the specified DFA
     */
    public static <S, I, A extends DFA<S, I> & InputAlphabetHolder<I>> CompactDFA<I> minimize(A dfa) {
        return HopcroftMinimizer.minimizeDFA(dfa);
    }

    /**
     * Computes whether the language of the given DFA is prefix-closed.
     * <p>
     * Assumes all states in the given {@link DFA} are reachable from the initial state.
     *
     * @param dfa
     *         the DFA to check
     * @param inputs
     *         the input symbols to consider
     * @param <I>
     *         input symbol type
     * @param <S>
     *         state type
     *
     * @return whether the DFA is prefix-closed
     */
    public static <S, I> boolean isPrefixClosed(DFA<S, I> dfa, Collection<I> inputs) {
        for (S s : dfa) {
            if (!dfa.isAccepting(s)) {
                for (I i : inputs) {
                    final S succ = dfa.getSuccessor(s, i);
                    if (succ != null && dfa.isAccepting(succ)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

    /**
     * Computes whether the given {@link DFA} accepts the empty language.
     * <p>
     * Assumes all states in the given {@link DFA} are reachable from the initial state.
     *
     * @param dfa
     *         the {@link DFA} to check
     * @param <S>
     *         state type
     *
     * @return whether the given {@link DFA} accepts the empty language
     */
    public static <S> boolean acceptsEmptyLanguage(DFA<S, ?> dfa) {
        for (S s : dfa) {
            if (dfa.isAccepting(s)) {
                return false;
            }
        }
        return true;
    }
}

1	/* Copyright (C) 2013-2024 TU Dortmund University
2	* This file is part of AutomataLib, http://www.automatalib.net/.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package net.automatalib.util.automaton.fsa;
17
18	import java.util.Collection;
19	import java.util.Objects;
20	import java.util.Set;
21
22	import net.automatalib.alphabet.Alphabet;
23	import net.automatalib.automaton.concept.InputAlphabetHolder;
24	import net.automatalib.automaton.fsa.DFA;
25	import net.automatalib.automaton.fsa.MutableDFA;
26	import net.automatalib.automaton.fsa.NFA;
27	import net.automatalib.automaton.fsa.impl.CompactDFA;
28	import net.automatalib.common.util.mapping.MutableMapping;
29	import net.automatalib.ts.acceptor.DeterministicAcceptorTS;
30	import net.automatalib.util.automaton.copy.AutomatonCopyMethod;
31	import net.automatalib.util.automaton.copy.AutomatonLowLevelCopy;
32	import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;
33	import net.automatalib.util.ts.acceptor.AcceptanceCombiner;
34	import net.automatalib.util.ts.acceptor.Acceptors;
35	import net.automatalib.util.ts.copy.TSCopy;
36	import net.automatalib.util.ts.traversal.TSTraversal;
37	import net.automatalib.util.ts.traversal.TSTraversalMethod;
38
39	/**
40	* Operations on {@link DFA}s.
41	* <p>
42	* Note that the methods provided by this class do not modify their input arguments. Such methods are instead provided
43	* by the {@link MutableDFAs} class. Furthermore, results are copied into new datastructures. For read-only views you
44	* may use the more generic {@link Acceptors} factory.
45	*/
46	public final class DFAs {
47
48	private DFAs() {
49	// prevent instantiation
50	}
51
52	/**
53	* Most general way of combining two DFAs. The behavior is the same as of the above {@link #combine(DFA, DFA,
54	* Collection, MutableDFA, AcceptanceCombiner)}, but the result automaton is automatically created as a {@link
55	* CompactDFA}.
56	*
57	* @param dfa1
58	* the first DFA
59	* @param dfa2
60	* the second DFA
61	* @param inputAlphabet
62	* the input alphabet
63	* @param combiner
64	* combination method for acceptance values
65	* @param <I>
66	* input symbol type
67	*
68	* @return a new DFA representing the combination of the specified DFA
69	*/
70	public static <I> CompactDFA<I> combine(DFA<?, I> dfa1,
71	DFA<?, I> dfa2,
72	Alphabet<I> inputAlphabet,
73	AcceptanceCombiner combiner) {
74	return combine(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet), combiner);	2✔
75	}
76
77	/**
78	* Most general way of combining two DFAs. The {@link AcceptanceCombiner} specified via the {@code combiner}
79	* parameter specifies how acceptance values of the DFAs will be combined to an acceptance value in the result DFA.
80	*
81	* @param dfa1
82	* the first DFA
83	* @param dfa2
84	* the second DFA
85	* @param inputs
86	* the input symbols to consider
87	* @param out
88	* the mutable DFA for storing the result
89	* @param combiner
90	* combination method for acceptance values
91	* @param <I>
92	* input symbol type
93	* @param <S>
94	* state type
95	* @param <A>
96	* automaton type
97	*
98	* @return {@code out}, for convenience
99	*/
100	public static <I, S, A extends MutableDFA<S, I>> A combine(DFA<?, I> dfa1,
101	DFA<?, I> dfa2,
102	Collection<? extends I> inputs,
103	A out,
104	AcceptanceCombiner combiner) {
105	DeterministicAcceptorTS<?, I> acc = Acceptors.combine(dfa1, dfa2, combiner);	2✔
106
107	TSCopy.copy(TSTraversalMethod.DEPTH_FIRST, acc, TSTraversal.NO_LIMIT, inputs, out);	2✔
108	return out;	2✔
109	}
110
111	/**
112	* Calculates the conjunction ("and") of two DFA, and returns the result as a new DFA.
113	*
114	* @param dfa1
115	* the first DFA
116	* @param dfa2
117	* the second DFA
118	* @param inputAlphabet
119	* the input alphabet
120	* @param <I>
121	* input symbol type
122	*
123	* @return a new DFA representing the conjunction of the specified DFA
124	*/
125	public static <I> CompactDFA<I> and(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
126	return and(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
127	}
128
129	/**
130	* Calculates the conjunction ("and") of two DFA, and stores the result in a given mutable DFA.
131	*
132	* @param dfa1
133	* the first DFA
134	* @param dfa2
135	* the second DFA
136	* @param inputs
137	* the input symbols to consider
138	* @param out
139	* a mutable DFA for storing the result
140	* @param <I>
141	* input symbol type
142	* @param <S>
143	* state type
144	* @param <A>
145	* automaton type
146	*
147	* @return {@code out}, for convenience
148	*/
149	public static <I, S, A extends MutableDFA<S, I>> A and(DFA<?, I> dfa1,
150	DFA<?, I> dfa2,
151	Collection<? extends I> inputs,
152	A out) {
153	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.AND);	2✔
154	}
155
156	/**
157	* Calculates the disjunction ("or") of two DFA, and returns the result as a new DFA.
158	*
159	* @param dfa1
160	* the first DFA
161	* @param dfa2
162	* the second DFA
163	* @param inputAlphabet
164	* the input alphabet
165	* @param <I>
166	* input symbol type
167	*
168	* @return a new DFA representing the conjunction of the specified DFA
169	*/
170	public static <I> CompactDFA<I> or(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
171	return or(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
172	}
173
174	/**
175	* Calculates the disjunction ("or") of two DFA, and stores the result in a given mutable DFA.
176	*
177	* @param dfa1
178	* the first DFA
179	* @param dfa2
180	* the second DFA
181	* @param inputs
182	* the input symbols to consider
183	* @param out
184	* a mutable DFA for storing the result
185	* @param <I>
186	* input symbol type
187	* @param <S>
188	* state type
189	* @param <A>
190	* automaton type
191	*
192	* @return {@code out}, for convenience
193	*/
194	public static <I, S, A extends MutableDFA<S, I>> A or(DFA<?, I> dfa1,
195	DFA<?, I> dfa2,
196	Collection<? extends I> inputs,
197	A out) {
198	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.OR);	2✔
199	}
200
201	/**
202	* Calculates the exclusive-or ("xor") of two DFA, and returns the result as a new DFA.
203	*
204	* @param dfa1
205	* the first DFA
206	* @param dfa2
207	* the second DFA
208	* @param inputAlphabet
209	* the input alphabet
210	* @param <I>
211	* input symbol type
212	*
213	* @return a new DFA representing the conjunction of the specified DFA
214	*/
215	public static <I> CompactDFA<I> xor(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
216	return xor(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
217	}
218
219	/**
220	* Calculates the exclusive-or ("xor") of two DFA, and stores the result in a given mutable DFA.
221	*
222	* @param dfa1
223	* the first DFA
224	* @param dfa2
225	* the second DFA
226	* @param inputs
227	* the input symbols to consider
228	* @param out
229	* a mutable DFA for storing the result
230	* @param <I>
231	* input symbol type
232	* @param <S>
233	* state type
234	* @param <A>
235	* automaton type
236	*
237	* @return {@code out}, for convenience
238	*/
239	public static <I, S, A extends MutableDFA<S, I>> A xor(DFA<?, I> dfa1,
240	DFA<?, I> dfa2,
241	Collection<? extends I> inputs,
242	A out) {
243	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.XOR);	2✔
244	}
245
246	/**
247	* Calculates the equivalence ("<=>") of two DFA, and returns the result as a new DFA.
248	*
249	* @param dfa1
250	* the first DFA
251	* @param dfa2
252	* the second DFA
253	* @param inputAlphabet
254	* the input alphabet
255	* @param <I>
256	* input symbol type
257	*
258	* @return a new DFA representing the conjunction of the specified DFA
259	*/
260	public static <I> CompactDFA<I> equiv(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
261	return equiv(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
262	}
263
264	/**
265	* Calculates the equivalence ("<=>") of two DFA, and stores the result in a given mutable DFA.
266	*
267	* @param dfa1
268	* the first DFA
269	* @param dfa2
270	* the second DFA
271	* @param inputs
272	* the input symbols to consider
273	* @param out
274	* a mutable DFA for storing the result
275	* @param <I>
276	* input symbol type
277	* @param <S>
278	* state type
279	* @param <A>
280	* automaton type
281	*
282	* @return {@code out}, for convenience
283	*/
284	public static <I, S, A extends MutableDFA<S, I>> A equiv(DFA<?, I> dfa1,
285	DFA<?, I> dfa2,
286	Collection<? extends I> inputs,
287	A out) {
288	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.EQUIV);	2✔
289	}
290
291	/**
292	* Calculates the implication ("=>") of two DFA, and returns the result as a new DFA.
293	*
294	* @param dfa1
295	* the first DFA
296	* @param dfa2
297	* the second DFA
298	* @param inputAlphabet
299	* the input alphabet
300	* @param <I>
301	* input symbol type
302	*
303	* @return a new DFA representing the conjunction of the specified DFA
304	*/
305	public static <I> CompactDFA<I> impl(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
306	return impl(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
307	}
308
309	/**
310	* Calculates the implication ("=>") of two DFA, and stores the result in a given mutable DFA.
311	*
312	* @param dfa1
313	* the first DFA
314	* @param dfa2
315	* the second DFA
316	* @param inputs
317	* the input symbols to consider
318	* @param out
319	* a mutable DFA for storing the result
320	* @param <I>
321	* input symbol type
322	* @param <S>
323	* state type
324	* @param <A>
325	* automaton type
326	*
327	* @return {@code out}, for convenience
328	*/
329	public static <I, S, A extends MutableDFA<S, I>> A impl(DFA<?, I> dfa1,
330	DFA<?, I> dfa2,
331	Collection<? extends I> inputs,
332	A out) {
333	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.IMPL);	2✔
334	}
335
336	/**
337	* Creates a trim DFA from the given input DFA. A DFA is trim if all of its states are accessible and
338	* co-accessible.
339	*
340	* @param dfa
341	* the input DFA
342	* @param inputAlphabet
343	* the input alphabet
344	* @param <I>
345	* input symbol type
346	*
347	* @return the trim DFA
348	*
349	* @see NFAs#accessibleStates(NFA, Collection)
350	* @see NFAs#coaccessibleStates(NFA, Collection)
351	*/
352	public static <I> CompactDFA<I> trim(DFA<?, I> dfa, Alphabet<I> inputAlphabet) {
353	return trim(dfa, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
354	}
355
356	/**
357	* 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
358	* states are accessible and co-accessible.
359	*
360	* @param dfa
361	* the input DFA
362	* @param inputs
363	* the input symbols to consider
364	* @param out
365	* the output NFA
366	* @param <SI>
367	* (input) state type
368	* @param <I>
369	* input symbol type
370	* @param <SO>
371	* (output) state type
372	* @param <A>
373	* (output) automaton type
374	*
375	* @return {@code out} for convenience
376	*
377	* @see NFAs#accessibleStates(NFA, Collection)
378	* @see NFAs#coaccessibleStates(NFA, Collection)
379	*/
380	public static <SI, I, SO, A extends MutableDFA<SO, I>> A trim(DFA<SI, I> dfa,
381	Collection<? extends I> inputs,
382	A out) {
383	final MutableMapping<SI, SO> mapping = dfa.createStaticStateMapping();	2✔
384	final SI init = dfa.getInitialState();	2✔
385
386	final Set<SI> states = NFAs.accessibleStates(dfa, inputs);	2✔
387	states.retainAll(NFAs.coaccessibleStates(dfa, inputs));	2✔
388
389	for (SI s : states) {	2✔
390	final SO so = out.addState(dfa.isAccepting(s));	2✔
391	out.setInitial(so, Objects.equals(init, s));	2✔
392	mapping.put(s, so);	2✔
393	}	2✔
394
395	for (SI s : states) {	2✔
396	for (I i : inputs) {	2✔
397	final SI t = dfa.getSuccessor(s, i);	2✔
398	if (states.contains(t)) {	2✔
399	out.addTransition(mapping.get(s), i, mapping.get(t));	2✔
400	}
401	}	2✔
402	}	2✔
403
404	return out;	2✔
405	}
406
407	/**
408	* Calculates the complement (negation) of a DFA, and returns the result as a new DFA.
409	* <p>
410	* Note that unlike {@link MutableDFA#flipAcceptance()}, undefined transitions are treated as leading to a rejecting
411	* sink state (and are thus turned into an accepting sink).
412	*
413	* @param dfa
414	* the DFA to complement
415	* @param inputAlphabet
416	* the input alphabet
417	* @param <I>
418	* input symbol type
419	*
420	* @return a new DFA representing the complement of the specified DFA
421	*/
422	public static <I> CompactDFA<I> complement(DFA<?, I> dfa, Alphabet<I> inputAlphabet) {
423	return complement(dfa, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
424	}
425
426	/**
427	* Calculates the complement (negation) of a DFA, and stores the result in a given mutable DFA.
428	* <p>
429	* Note that unlike {@link MutableDFA#flipAcceptance()}, undefined transitions are treated as leading to a rejecting
430	* sink state (and are thus turned into an accepting sink).
431	*
432	* @param dfa
433	* the DFA to complement
434	* @param inputs
435	* the input symbols to consider
436	* @param out
437	* a mutable DFA for storing the result
438	* @param <I>
439	* input symbol type
440	* @param <S>
441	* state type
442	* @param <A>
443	* automaton type
444	*
445	* @return {@code out}, for convenience
446	*/
447	public static <I, S, A extends MutableDFA<S, I>> A complement(DFA<?, I> dfa,
448	Collection<? extends I> inputs,
449	A out) {
450	AutomatonLowLevelCopy.copy(AutomatonCopyMethod.STATE_BY_STATE,	2✔
451	dfa,
452	inputs,
453	out,
454	b -> b == null \|\| !b,	2✔
455	t -> null);	2✔
456	MutableDFAs.complete(out, inputs, false, true);	2✔
457	return out;	2✔
458	}
459
460	public static <I> CompactDFA<I> complete(DFA<?, I> dfa, Alphabet<I> inputs) {
461	return complete(dfa, inputs, new CompactDFA<>(inputs));	2✔
462	}
463
464	public static <I, S, A extends MutableDFA<S, I>> A complete(DFA<?, I> dfa, Collection<? extends I> inputs, A out) {
465	AutomatonLowLevelCopy.copy(AutomatonCopyMethod.DFS, dfa, inputs, out);	2✔
466	MutableDFAs.complete(out, inputs, true);	2✔
467	return out;	2✔
468	}
469
470	/**
471	* Minimizes the given DFA over the given alphabet. This method does not modify the given DFA, but returns the
472	* minimized version as a new instance.
473	* <p>
474	* <b>Note:</b> the DFA must be completely specified.
475	*
476	* @param dfa
477	* the DFA to be minimized
478	* @param alphabet
479	* the input alphabet to consider for minimization (this will also be the input alphabet of the resulting
480	* automaton)
481	* @param <I>
482	* input symbol type
483	*
484	* @return a minimized version of the specified DFA
485	*/
486	public static <I> CompactDFA<I> minimize(DFA<?, I> dfa, Alphabet<I> alphabet) {
NEW 487	return HopcroftMinimizer.minimizeDFA(dfa, alphabet);	×
488	}
489
490	/**
491	* Minimizes the given DFA. This method does not modify the given DFA, but returns the minimized version as a new
492	* instance.
493	* <p>
494	* <b>Note:</b> the DFA must be completely specified
495	*
496	* @param dfa
497	* the DFA to be minimized
498	* @param <I>
499	* input symbol type
500	* @param <S>
501	* state type
502	* @param <A>
503	* automaton type
504	*
505	* @return a minimized version of the specified DFA
506	*/
507	public static <S, I, A extends DFA<S, I> & InputAlphabetHolder<I>> CompactDFA<I> minimize(A dfa) {
NEW 508	return HopcroftMinimizer.minimizeDFA(dfa);	×
509	}
510
511	/**
512	* Computes whether the language of the given DFA is prefix-closed.
513	* <p>
514	* Assumes all states in the given {@link DFA} are reachable from the initial state.
515	*
516	* @param dfa
517	* the DFA to check
518	* @param inputs
519	* the input symbols to consider
520	* @param <I>
521	* input symbol type
522	* @param <S>
523	* state type
524	*
525	* @return whether the DFA is prefix-closed
526	*/
527	public static <S, I> boolean isPrefixClosed(DFA<S, I> dfa, Collection<I> inputs) {
528	for (S s : dfa) {	2✔
529	if (!dfa.isAccepting(s)) {	2✔
530	for (I i : inputs) {	2✔
531	final S succ = dfa.getSuccessor(s, i);	2✔
532	if (succ != null && dfa.isAccepting(succ)) {	2✔
533	return false;	2✔
534	}
535	}	2✔
536	}
537	}	2✔
538
539	return true;	2✔
540	}
541
542	/**
543	* Computes whether the given {@link DFA} accepts the empty language.
544	* <p>
545	* Assumes all states in the given {@link DFA} are reachable from the initial state.
546	*
547	* @param dfa
548	* the {@link DFA} to check
549	* @param <S>
550	* state type
551	*
552	* @return whether the given {@link DFA} accepts the empty language
553	*/
554	public static <S> boolean acceptsEmptyLanguage(DFA<S, ?> dfa) {
555	for (S s : dfa) {	2✔
556	if (dfa.isAccepting(s)) {	2✔
557	return false;	2✔
558	}
559	}	2✔
560	return true;	2✔
561	}
562	}

LearnLib / automatalib / 12304577693

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous