12562237475

Committed 31 Dec 2024 04:28PM UTC coverage: 91.542% (+0.01%) from 91.532%

Build # 12562237475

Build Type

push

github

Committed by

mtf90

Commit Message

widen type-constraint on AbstractBasicLinkedListEntry

Run Details

1 of 1 new or added line in 1 file covered. (100.0%)

4 existing lines in 2 files now uncovered.

16582 of 18114 relevant lines covered (91.54%)

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 via product construction. 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 via product construction. 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 DFAs via product construction 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 DFAs via product construction 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 DFAs via product construction 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 DFAs via product construction 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 DFAs via product construction 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 DFAs via product construction 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 DFAs via product construction 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 DFAs via product construction 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 DFAs via product construction 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 DFAs via product construction 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 via product construction. The behavior is the same as of the above
54	* {@link #combine(DFA, DFA, Collection, MutableDFA, AcceptanceCombiner)}, but the result automaton is automatically
55	* created as a {@link 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 via product construction. The {@link AcceptanceCombiner} specified via the
79	* {@code combiner} parameter specifies how acceptance values of the DFAs will be combined to an acceptance value in
80	* the result DFA.
81	*
82	* @param dfa1
83	* the first DFA
84	* @param dfa2
85	* the second DFA
86	* @param inputs
87	* the input symbols to consider
88	* @param out
89	* the mutable DFA for storing the result
90	* @param combiner
91	* combination method for acceptance values
92	* @param <I>
93	* input symbol type
94	* @param <S>
95	* state type
96	* @param <A>
97	* automaton type
98	*
99	* @return {@code out}, for convenience
100	*/
101	public static <I, S, A extends MutableDFA<S, I>> A combine(DFA<?, I> dfa1,
102	DFA<?, I> dfa2,
103	Collection<? extends I> inputs,
104	A out,
105	AcceptanceCombiner combiner) {
106	DeterministicAcceptorTS<?, I> acc = Acceptors.combine(dfa1, dfa2, combiner);	2✔
107
108	TSCopy.copy(TSTraversalMethod.DEPTH_FIRST, acc, TSTraversal.NO_LIMIT, inputs, out);	2✔
109	return out;	2✔
110	}
111
112	/**
113	* Calculates the conjunction ("and") of two DFAs via product construction and returns the result as a new DFA.
114	*
115	* @param dfa1
116	* the first DFA
117	* @param dfa2
118	* the second DFA
119	* @param inputAlphabet
120	* the input alphabet
121	* @param <I>
122	* input symbol type
123	*
124	* @return a new DFA representing the conjunction of the specified DFA
125	*/
126	public static <I> CompactDFA<I> and(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
127	return and(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
128	}
129
130	/**
131	* Calculates the conjunction ("and") of two DFAs via product construction and stores the result in a given mutable
132	* DFA.
133	*
134	* @param dfa1
135	* the first DFA
136	* @param dfa2
137	* the second DFA
138	* @param inputs
139	* the input symbols to consider
140	* @param out
141	* a mutable DFA for storing the result
142	* @param <I>
143	* input symbol type
144	* @param <S>
145	* state type
146	* @param <A>
147	* automaton type
148	*
149	* @return {@code out}, for convenience
150	*/
151	public static <I, S, A extends MutableDFA<S, I>> A and(DFA<?, I> dfa1,
152	DFA<?, I> dfa2,
153	Collection<? extends I> inputs,
154	A out) {
155	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.AND);	2✔
156	}
157
158	/**
159	* Calculates the disjunction ("or") of two DFAs via product construction and returns the result as a new DFA.
160	*
161	* @param dfa1
162	* the first DFA
163	* @param dfa2
164	* the second DFA
165	* @param inputAlphabet
166	* the input alphabet
167	* @param <I>
168	* input symbol type
169	*
170	* @return a new DFA representing the conjunction of the specified DFA
171	*/
172	public static <I> CompactDFA<I> or(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
173	return or(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
174	}
175
176	/**
177	* Calculates the disjunction ("or") of two DFAs via product construction and stores the result in a given mutable
178	* DFA.
179	*
180	* @param dfa1
181	* the first DFA
182	* @param dfa2
183	* the second DFA
184	* @param inputs
185	* the input symbols to consider
186	* @param out
187	* a mutable DFA for storing the result
188	* @param <I>
189	* input symbol type
190	* @param <S>
191	* state type
192	* @param <A>
193	* automaton type
194	*
195	* @return {@code out}, for convenience
196	*/
197	public static <I, S, A extends MutableDFA<S, I>> A or(DFA<?, I> dfa1,
198	DFA<?, I> dfa2,
199	Collection<? extends I> inputs,
200	A out) {
201	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.OR);	2✔
202	}
203
204	/**
205	* Calculates the exclusive-or ("xor") of two DFAs via product construction and returns the result as a new DFA.
206	*
207	* @param dfa1
208	* the first DFA
209	* @param dfa2
210	* the second DFA
211	* @param inputAlphabet
212	* the input alphabet
213	* @param <I>
214	* input symbol type
215	*
216	* @return a new DFA representing the conjunction of the specified DFA
217	*/
218	public static <I> CompactDFA<I> xor(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
219	return xor(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
220	}
221
222	/**
223	* Calculates the exclusive-or ("xor") of two DFAs via product construction and stores the result in a given mutable
224	* DFA.
225	*
226	* @param dfa1
227	* the first DFA
228	* @param dfa2
229	* the second DFA
230	* @param inputs
231	* the input symbols to consider
232	* @param out
233	* a mutable DFA for storing the result
234	* @param <I>
235	* input symbol type
236	* @param <S>
237	* state type
238	* @param <A>
239	* automaton type
240	*
241	* @return {@code out}, for convenience
242	*/
243	public static <I, S, A extends MutableDFA<S, I>> A xor(DFA<?, I> dfa1,
244	DFA<?, I> dfa2,
245	Collection<? extends I> inputs,
246	A out) {
247	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.XOR);	2✔
248	}
249
250	/**
251	* Calculates the equivalence ("<=>") of two DFAs via product construction and returns the result as a new
252	* DFA.
253	*
254	* @param dfa1
255	* the first DFA
256	* @param dfa2
257	* the second DFA
258	* @param inputAlphabet
259	* the input alphabet
260	* @param <I>
261	* input symbol type
262	*
263	* @return a new DFA representing the conjunction of the specified DFA
264	*/
265	public static <I> CompactDFA<I> equiv(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
266	return equiv(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
267	}
268
269	/**
270	* Calculates the equivalence ("<=>") of two DFAs via product construction and stores the result in a given
271	* mutable DFA.
272	*
273	* @param dfa1
274	* the first DFA
275	* @param dfa2
276	* the second DFA
277	* @param inputs
278	* the input symbols to consider
279	* @param out
280	* a mutable DFA for storing the result
281	* @param <I>
282	* input symbol type
283	* @param <S>
284	* state type
285	* @param <A>
286	* automaton type
287	*
288	* @return {@code out}, for convenience
289	*/
290	public static <I, S, A extends MutableDFA<S, I>> A equiv(DFA<?, I> dfa1,
291	DFA<?, I> dfa2,
292	Collection<? extends I> inputs,
293	A out) {
294	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.EQUIV);	2✔
295	}
296
297	/**
298	* Calculates the implication ("=>") of two DFAs via product construction and returns the result as a new DFA.
299	*
300	* @param dfa1
301	* the first DFA
302	* @param dfa2
303	* the second DFA
304	* @param inputAlphabet
305	* the input alphabet
306	* @param <I>
307	* input symbol type
308	*
309	* @return a new DFA representing the conjunction of the specified DFA
310	*/
311	public static <I> CompactDFA<I> impl(DFA<?, I> dfa1, DFA<?, I> dfa2, Alphabet<I> inputAlphabet) {
312	return impl(dfa1, dfa2, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
313	}
314
315	/**
316	* Calculates the implication ("=>") of two DFAs via product construction and stores the result in a given
317	* mutable DFA.
318	*
319	* @param dfa1
320	* the first DFA
321	* @param dfa2
322	* the second DFA
323	* @param inputs
324	* the input symbols to consider
325	* @param out
326	* a mutable DFA for storing the result
327	* @param <I>
328	* input symbol type
329	* @param <S>
330	* state type
331	* @param <A>
332	* automaton type
333	*
334	* @return {@code out}, for convenience
335	*/
336	public static <I, S, A extends MutableDFA<S, I>> A impl(DFA<?, I> dfa1,
337	DFA<?, I> dfa2,
338	Collection<? extends I> inputs,
339	A out) {
340	return combine(dfa1, dfa2, inputs, out, AcceptanceCombiner.IMPL);	2✔
341	}
342
343	/**
344	* Creates a trim DFA from the given input DFA. A DFA is trim if all of its states are accessible and
345	* co-accessible.
346	*
347	* @param dfa
348	* the input DFA
349	* @param inputAlphabet
350	* the input alphabet
351	* @param <I>
352	* input symbol type
353	*
354	* @return the trim DFA
355	*
356	* @see NFAs#accessibleStates(NFA, Collection)
357	* @see NFAs#coaccessibleStates(NFA, Collection)
358	*/
359	public static <I> CompactDFA<I> trim(DFA<?, I> dfa, Alphabet<I> inputAlphabet) {
360	return trim(dfa, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
361	}
362
363	/**
364	* 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
365	* states are accessible and co-accessible.
366	*
367	* @param dfa
368	* the input DFA
369	* @param inputs
370	* the input symbols to consider
371	* @param out
372	* the output NFA
373	* @param <SI>
374	* (input) state type
375	* @param <I>
376	* input symbol type
377	* @param <SO>
378	* (output) state type
379	* @param <A>
380	* (output) automaton type
381	*
382	* @return {@code out} for convenience
383	*
384	* @see NFAs#accessibleStates(NFA, Collection)
385	* @see NFAs#coaccessibleStates(NFA, Collection)
386	*/
387	public static <SI, I, SO, A extends MutableDFA<SO, I>> A trim(DFA<SI, I> dfa,
388	Collection<? extends I> inputs,
389	A out) {
390	final MutableMapping<SI, SO> mapping = dfa.createStaticStateMapping();	2✔
391	final SI init = dfa.getInitialState();	2✔
392
393	final Set<SI> states = NFAs.accessibleStates(dfa, inputs);	2✔
394	states.retainAll(NFAs.coaccessibleStates(dfa, inputs));	2✔
395
396	for (SI s : states) {	2✔
397	final SO so = out.addState(dfa.isAccepting(s));	2✔
398	out.setInitial(so, Objects.equals(init, s));	2✔
399	mapping.put(s, so);	2✔
400	}	2✔
401
402	for (SI s : states) {	2✔
403	for (I i : inputs) {	2✔
404	final SI t = dfa.getSuccessor(s, i);	2✔
405	if (states.contains(t)) {	2✔
406	out.addTransition(mapping.get(s), i, mapping.get(t));	2✔
407	}
408	}	2✔
409	}	2✔
410
411	return out;	2✔
412	}
413
414	/**
415	* Calculates the complement (negation) of a DFA and returns the result as a new DFA.
416	* <p>
417	* Note that unlike {@link MutableDFA#flipAcceptance()}, undefined transitions are treated as leading to a rejecting
418	* sink state (and are thus turned into an accepting sink).
419	*
420	* @param dfa
421	* the DFA to complement
422	* @param inputAlphabet
423	* the input alphabet
424	* @param <I>
425	* input symbol type
426	*
427	* @return a new DFA representing the complement of the specified DFA
428	*/
429	public static <I> CompactDFA<I> complement(DFA<?, I> dfa, Alphabet<I> inputAlphabet) {
430	return complement(dfa, inputAlphabet, new CompactDFA<>(inputAlphabet));	2✔
431	}
432
433	/**
434	* Calculates the complement (negation) of a DFA, and stores the result in a given mutable DFA.
435	* <p>
436	* Note that unlike {@link MutableDFA#flipAcceptance()}, undefined transitions are treated as leading to a rejecting
437	* sink state (and are thus turned into an accepting sink).
438	*
439	* @param dfa
440	* the DFA to complement
441	* @param inputs
442	* the input symbols to consider
443	* @param out
444	* a mutable DFA for storing the result
445	* @param <I>
446	* input symbol type
447	* @param <S>
448	* state type
449	* @param <A>
450	* automaton type
451	*
452	* @return {@code out}, for convenience
453	*/
454	public static <I, S, A extends MutableDFA<S, I>> A complement(DFA<?, I> dfa,
455	Collection<? extends I> inputs,
456	A out) {
457	AutomatonLowLevelCopy.copy(AutomatonCopyMethod.STATE_BY_STATE,	2✔
458	dfa,
459	inputs,
460	out,
461	b -> b == null \|\| !b,	2✔
462	t -> null);	2✔
463	MutableDFAs.complete(out, inputs, false, true);	2✔
464	return out;	2✔
465	}
466
467	public static <I> CompactDFA<I> complete(DFA<?, I> dfa, Alphabet<I> inputs) {
468	return complete(dfa, inputs, new CompactDFA<>(inputs));	2✔
469	}
470
471	public static <I, S, A extends MutableDFA<S, I>> A complete(DFA<?, I> dfa, Collection<? extends I> inputs, A out) {
472	AutomatonLowLevelCopy.copy(AutomatonCopyMethod.DFS, dfa, inputs, out);	2✔
473	MutableDFAs.complete(out, inputs, true);	2✔
474	return out;	2✔
475	}
476
477	/**
478	* Minimizes the given DFA over the given alphabet. This method does not modify the given DFA, but returns the
479	* minimized version as a new instance.
480	* <p>
481	* <b>Note:</b> the DFA must be completely specified.
482	*
483	* @param dfa
484	* the DFA to be minimized
485	* @param alphabet
486	* the input alphabet to consider for minimization (this will also be the input alphabet of the resulting
487	* automaton)
488	* @param <I>
489	* input symbol type
490	*
491	* @return a minimized version of the specified DFA
492	*/
493	public static <I> CompactDFA<I> minimize(DFA<?, I> dfa, Alphabet<I> alphabet) {
UNCOV 494	return HopcroftMinimizer.minimizeDFA(dfa, alphabet);	×
495	}
496
497	/**
498	* Minimizes the given DFA. This method does not modify the given DFA, but returns the minimized version as a new
499	* instance.
500	* <p>
501	* <b>Note:</b> the DFA must be completely specified
502	*
503	* @param dfa
504	* the DFA to be minimized
505	* @param <I>
506	* input symbol type
507	* @param <S>
508	* state type
509	* @param <A>
510	* automaton type
511	*
512	* @return a minimized version of the specified DFA
513	*/
514	public static <S, I, A extends DFA<S, I> & InputAlphabetHolder<I>> CompactDFA<I> minimize(A dfa) {
UNCOV 515	return HopcroftMinimizer.minimizeDFA(dfa);	×
516	}
517
518	/**
519	* Computes whether the language of the given DFA is prefix-closed.
520	* <p>
521	* Assumes all states in the given {@link DFA} are reachable from the initial state.
522	*
523	* @param dfa
524	* the DFA to check
525	* @param inputs
526	* the input symbols to consider
527	* @param <I>
528	* input symbol type
529	* @param <S>
530	* state type
531	*
532	* @return whether the DFA is prefix-closed
533	*/
534	public static <S, I> boolean isPrefixClosed(DFA<S, I> dfa, Collection<I> inputs) {
535	for (S s : dfa) {	2✔
536	if (!dfa.isAccepting(s)) {	2✔
537	for (I i : inputs) {	2✔
538	final S succ = dfa.getSuccessor(s, i);	2✔
539	if (succ != null && dfa.isAccepting(succ)) {	2✔
540	return false;	2✔
541	}
542	}	2✔
543	}
544	}	2✔
545
546	return true;	2✔
547	}
548
549	/**
550	* Computes whether the given {@link DFA} accepts the empty language.
551	* <p>
552	* Assumes all states in the given {@link DFA} are reachable from the initial state.
553	*
554	* @param dfa
555	* the {@link DFA} to check
556	* @param <S>
557	* state type
558	*
559	* @return whether the given {@link DFA} accepts the empty language
560	*/
561	public static <S> boolean acceptsEmptyLanguage(DFA<S, ?> dfa) {
562	for (S s : dfa) {	2✔
563	if (dfa.isAccepting(s)) {	2✔
564	return false;	2✔
565	}
566	}	2✔
567	return true;	2✔
568	}
569	}

LearnLib / automatalib / 12562237475

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