12651580329

Committed 07 Jan 2025 12:29PM UTC coverage: 91.569% (+0.03%) from 91.542%

Build # 12651580329

Build Type

push

github

Committed by

web-flow

Commit Message

Update dependencies (#85)

* bump basic dependency versions

* bump checkstyle + cleanups

* bump spotbugs + cleanups

* bump pmd + cleanups

* bump checkerframework + cleanups

* some more cleanups

* ExceptionUtil: support nulls

* improve comments

* cleanup naming + formatting

* formatting

* formatting

* do not fail on javadoc warnings

completness of documentation is now checked by checkstyle and we would have to disable failing anyways when moving on to JDK 17

Run Details

192 of 217 new or added lines in 63 files covered. (88.48%)

4 existing lines in 4 files now uncovered.

16573 of 18099 relevant lines covered (91.57%)

1.69 hits per line

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

96.4

/util/src/main/java/net/automatalib/util/automaton/fsa/NFAs.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.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.alphabet.impl.MapAlphabet;
import net.automatalib.automaton.concept.InputAlphabetHolder;
import net.automatalib.automaton.fsa.MutableDFA;
import net.automatalib.automaton.fsa.MutableNFA;
import net.automatalib.automaton.fsa.NFA;
import net.automatalib.automaton.fsa.impl.CompactDFA;
import net.automatalib.automaton.fsa.impl.CompactNFA;
import net.automatalib.common.util.HashUtil;
import net.automatalib.common.util.mapping.Mapping;
import net.automatalib.common.util.mapping.MutableMapping;
import net.automatalib.ts.AcceptorPowersetViewTS;
import net.automatalib.ts.acceptor.AcceptorTS;
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 NFA}s.
 * <p>
 * Note that the methods provided by this class do not modify their input arguments. Furthermore, results are copied
 * into new datastructures. For read-only views you may use the more generic {@link Acceptors} factory.
 */
public final class NFAs {

    private NFAs() {
        // prevent instantiation
    }

    /**
     * Calculates the conjunction ("and") of two NFAs via product construction and returns the result as a new NFA.
     *
     * @param nfa1
     *         the first NFA
     * @param nfa2
     *         the second NFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return a new NFA representing the conjunction of the specified NFA
     */
    public static <I> CompactNFA<I> and(NFA<?, I> nfa1, NFA<?, I> nfa2, Alphabet<I> inputAlphabet) {
        return and(nfa1, nfa2, inputAlphabet, new CompactNFA<>(inputAlphabet));
    }

    /**
     * Calculates the conjunction ("and") of two NFAs via product construction and stores the result in a given mutable
     * NFA.
     *
     * @param nfa1
     *         the first NFA
     * @param nfa2
     *         the second NFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable NFA 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 MutableNFA<S, I>> A and(NFA<?, I> nfa1,
                                                           NFA<?, I> nfa2,
                                                           Collection<? extends I> inputs,
                                                           A out) {
        AcceptorTS<?, I> acc = Acceptors.combine(nfa1, nfa2, AcceptanceCombiner.AND);

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

    /**
     * Calculates the disjunction ("or") of two NFAs by merging their states and transitions. Returns the result as a
     * new NFA.
     *
     * @param nfa1
     *         the first NFA
     * @param nfa2
     *         the second NFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return a new NFA representing the conjunction of the specified NFA
     */
    public static <I> CompactNFA<I> or(NFA<?, I> nfa1, NFA<?, I> nfa2, Alphabet<I> inputAlphabet) {
        return or(nfa1, nfa2, inputAlphabet, new CompactNFA<>(inputAlphabet));
    }

    /**
     * Calculates the disjunction ("or") of two NFAs by merging their states and transitions. Stores the result in a
     * given mutable NFA.
     *
     * @param nfa1
     *         the first NFA
     * @param nfa2
     *         the second NFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable NFA 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 MutableNFA<S, I>> A or(NFA<?, I> nfa1,
                                                          NFA<?, I> nfa2,
                                                          Collection<? extends I> inputs,
                                                          A out) {
        MutableNFAs.or(out, nfa1, inputs);
        MutableNFAs.or(out, nfa2, inputs);

        return out;
    }

    /**
     * Creates an NFA for the reverse language of the given input NFA.
     *
     * @param nfa
     *         the input NFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return the reversed NFA
     */
    public static <I> CompactNFA<I> reverse(NFA<?, I> nfa, Alphabet<I> inputAlphabet) {
        final CompactNFA<I> result = new CompactNFA<>(inputAlphabet, nfa.size());
        reverse(nfa, inputAlphabet, result);
        return result;
    }

    /**
     * Writes an NFA for the reverse language of the given input NFA into the given output NFA.
     *
     * @param nfa
     *         the input NFA
     * @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 a mapping from output states to their original input states
     */
    public static <SI, I, SO, A extends MutableNFA<SO, I>> Mapping<SO, SI> reverse(NFA<SI, I> nfa,
                                                                                   Collection<? extends I> inputs,
                                                                                   A out) {
        final Set<SI> initialStates = nfa.getInitialStates();
        final MutableMapping<SI, SO> mapping = nfa.createStaticStateMapping();
        final MutableMapping<SO, SI> reverseMapping = out.createDynamicStateMapping();

        // accepting states are initial states and vice versa
        for (SI si : nfa) {
            final SO so = out.addState(initialStates.contains(si));
            out.setInitial(so, nfa.isAccepting(si));
            mapping.put(si, so);
            reverseMapping.put(so, si);
        }

        // reverse transitions
        for (SI s1 : nfa) {
            for (I a : inputs) {
                for (SI s2 : nfa.getTransitions(s1, a)) {
                    out.addTransition(mapping.get(s2), a, mapping.get(s1));
                }
            }
        }

        return reverseMapping;
    }

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

    /**
     * Creates a trim NFA from the given input NFA and writes it to the given output NFA. An NFA is trim if all of its
     * states are accessible and co-accessible.
     *
     * @param nfa
     *         the input NFA
     * @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 #accessibleStates(NFA, Collection)
     * @see #coaccessibleStates(NFA, Collection)
     */
    public static <SI, I, SO, A extends MutableNFA<SO, I>> A trim(NFA<SI, I> nfa,
                                                                  Collection<? extends I> inputs,
                                                                  A out) {
        final MutableMapping<SI, SO> mapping = nfa.createStaticStateMapping();
        final Set<SI> inits = nfa.getInitialStates();

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

        for (SI s : states) {
            final SO so = out.addState(nfa.isAccepting(s));
            out.setInitial(so, inits.contains(s));
            mapping.put(s, so);
        }

        for (SI s : states) {
            for (I i : inputs) {
                for (SI t : nfa.getTransitions(s, i)) {
                    if (states.contains(t)) {
                        out.addTransition(mapping.get(s), i, mapping.get(t));
                    }
                }
            }
        }

        return out;
    }

    /**
     * Returns for a given NFA the set of accessible states. A state is accessible if it can be reached by an initial
     * state.
     *
     * @param nfa
     *         the input NFA
     * @param inputs
     *         the input symbols to consider
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     *
     * @return the set of accessible states
     */
    public static <S, I> Set<S> accessibleStates(NFA<S, I> nfa, Collection<? extends I> inputs) {

        final Set<S> inits = nfa.getInitialStates();
        final Deque<S> deque = new ArrayDeque<>(inits);
        final Set<S> found = new HashSet<>(inits);

        while (!deque.isEmpty()) {
            final S curr = deque.pop();
            for (I sym : inputs) {
                for (S succ : nfa.getSuccessors(curr, sym)) {
                    if (found.add(succ)) {
                        deque.push(succ);
                    }
                }
            }
        }

        return found;
    }

    /**
     * Returns for a given NFA the set of co-accessible states. A state is co-accessible if it reaches an accepting
     * state.
     *
     * @param nfa
     *         the input NFA
     * @param inputs
     *         the input symbols to consider
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     *
     * @return the set of co-accessible states
     */
    public static <S, I> Set<S> coaccessibleStates(NFA<S, I> nfa, Collection<? extends I> inputs) {

        final CompactNFA<I> out = new CompactNFA<>(new MapAlphabet<>(inputs), nfa.size());
        final Mapping<Integer, S> mapping = reverse(nfa, inputs, out);
        final Set<Integer> states = accessibleStates(out, inputs);

        final Set<S> result = new HashSet<>(HashUtil.capacity(states.size()));

        for (Integer s : states) {
            result.add(mapping.get(s));
        }

        return result;
    }

    /**
     * Determinizes the given NFA, and returns the result as a new complete DFA.
     *
     * @param nfa
     *         the original NFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return the determinized NFA
     */
    public static <I> CompactDFA<I> determinize(NFA<?, I> nfa, Alphabet<I> inputAlphabet) {
        return determinize(nfa, inputAlphabet, false, true);
    }

    /**
     * Determinizes the given NFA, and returns the result as a new DFA.
     *
     * @param nfa
     *         the original NFA
     * @param inputAlphabet
     *         the input alphabet
     * @param partial
     *         allows the new DFA to be partial
     * @param minimize
     *         whether to minimize the DFA
     * @param <I>
     *         input symbol type
     *
     * @return the determinized NFA
     */
    public static <I> CompactDFA<I> determinize(NFA<?, I> nfa,
                                                Alphabet<I> inputAlphabet,
                                                boolean partial,
                                                boolean minimize) {
        CompactDFA<I> result = new CompactDFA<>(inputAlphabet);
        determinize(nfa, inputAlphabet, result, partial, minimize);
        return result;
    }

    /**
     * Determinizes the given NFA, and stores the result in a given mutable DFA.
     *
     * @param nfa
     *         the original NFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable DFA for storing the result
     * @param partial
     *         allows the new DFA to be partial
     * @param minimize
     *         whether to minimize the DFA
     * @param <I>
     *         input symbol type
     */
    public static <I> void determinize(NFA<?, I> nfa,
                                       Collection<? extends I> inputs,
                                       MutableDFA<?, I> out,
                                       boolean partial,
                                       boolean minimize) {
        doDeterminize(nfa.powersetView(), inputs, out, partial);
        if (minimize) {
            HopcroftMinimizer.minimizeDFAInvasive(out, inputs);
        }
    }

    /**
     * Determinizes the given NFA, and returns the result as a new DFA.
     *
     * @param nfa
     *         the original NFA
     * @param <I>
     *         input symbol type
     * @param <A>
     *         automaton type
     *
     * @return the determinized NFA
     */
    public static <I, A extends NFA<?, I> & InputAlphabetHolder<I>> CompactDFA<I> determinize(A nfa) {
        return determinize(nfa, false, true);
    }

    /**
     * Determinizes the given NFA, and returns the result as a new DFA.
     *
     * @param nfa
     *         the original NFA
     * @param partial
     *         allows the new DFA to be partial
     * @param minimize
     *         whether to minimize the DFA
     * @param <I>
     *         input symbol type
     * @param <A>
     *         automaton type
     *
     * @return the determinized NFA
     */
    public static <I, A extends NFA<?, I> & InputAlphabetHolder<I>> CompactDFA<I> determinize(A nfa,
                                                                                              boolean partial,
                                                                                              boolean minimize) {
        return determinize(nfa, nfa.getInputAlphabet(), partial, minimize);
    }

    /**
     * Determinizes the given NFA, and stores the result in a given mutable DFA.
     *
     * @param nfa
     *         the original NFA
     * @param inputs
     *         the input symbols to consider
     * @param out
     *         a mutable DFA for storing the result
     * @param <I>
     *         input symbol type
     */
    public static <I> void determinize(NFA<?, I> nfa, Collection<? extends I> inputs, MutableDFA<?, I> out) {
        determinize(nfa, inputs, out, false, true);
    }

    private static <I, SI, SO> void doDeterminize(AcceptorPowersetViewTS<SI, I, ?> powerset,
                                                  Collection<? extends I> inputs,
                                                  MutableDFA<SO, I> out,
                                                  boolean partial) {
        Map<SI, SO> outStateMap = new HashMap<>();
        Deque<DeterminizeRecord<SI, SO>> stack = new ArrayDeque<>();

        final SI init = powerset.getInitialState();

        if (init == null) {
            return;
        }

        final boolean initAcc = powerset.isAccepting(init);
        final SO initOut = out.addInitialState(initAcc);

        outStateMap.put(init, initOut);

        stack.push(new DeterminizeRecord<>(init, initOut));

        while (!stack.isEmpty()) {
            DeterminizeRecord<SI, SO> curr = stack.pop();

            SI inState = curr.inputState;
            SO outState = curr.outputState;

            for (I sym : inputs) {
                final SI succ = powerset.getSuccessor(inState, sym);

                if (succ != null) {
                    SO outSucc = outStateMap.get(succ);
                    if (outSucc == null) {
                        // add new state to DFA and to stack
                        outSucc = out.addState(powerset.isAccepting(succ));
                        outStateMap.put(succ, outSucc);
                        stack.push(new DeterminizeRecord<>(succ, outSucc));
                    }
                    out.setTransition(outState, sym, outSucc);
                } else if (!partial) {
                    throw new IllegalStateException("Cannot create a total DFA from a partial powerset view");
                }
            }
        }
    }

    private static final class DeterminizeRecord<SI, SO> {

        private final SI inputState;
        private final SO outputState;

        DeterminizeRecord(SI inputState, SO outputState) {
            this.inputState = inputState;
            this.outputState = outputState;
        }
    }
}

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.ArrayDeque;
19	import java.util.Collection;
20	import java.util.Deque;
21	import java.util.HashMap;
22	import java.util.HashSet;
23	import java.util.Map;
24	import java.util.Set;
25
26	import net.automatalib.alphabet.Alphabet;
27	import net.automatalib.alphabet.impl.MapAlphabet;
28	import net.automatalib.automaton.concept.InputAlphabetHolder;
29	import net.automatalib.automaton.fsa.MutableDFA;
30	import net.automatalib.automaton.fsa.MutableNFA;
31	import net.automatalib.automaton.fsa.NFA;
32	import net.automatalib.automaton.fsa.impl.CompactDFA;
33	import net.automatalib.automaton.fsa.impl.CompactNFA;
34	import net.automatalib.common.util.HashUtil;
35	import net.automatalib.common.util.mapping.Mapping;
36	import net.automatalib.common.util.mapping.MutableMapping;
37	import net.automatalib.ts.AcceptorPowersetViewTS;
38	import net.automatalib.ts.acceptor.AcceptorTS;
39	import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;
40	import net.automatalib.util.ts.acceptor.AcceptanceCombiner;
41	import net.automatalib.util.ts.acceptor.Acceptors;
42	import net.automatalib.util.ts.copy.TSCopy;
43	import net.automatalib.util.ts.traversal.TSTraversal;
44	import net.automatalib.util.ts.traversal.TSTraversalMethod;
45
46	/**
47	* Operations on {@link NFA}s.
48	* <p>
49	* Note that the methods provided by this class do not modify their input arguments. Furthermore, results are copied
50	* into new datastructures. For read-only views you may use the more generic {@link Acceptors} factory.
51	*/
52	public final class NFAs {
53
54	private NFAs() {
55	// prevent instantiation
56	}
57
58	/**
59	* Calculates the conjunction ("and") of two NFAs via product construction and returns the result as a new NFA.
60	*
61	* @param nfa1
62	* the first NFA
63	* @param nfa2
64	* the second NFA
65	* @param inputAlphabet
66	* the input alphabet
67	* @param <I>
68	* input symbol type
69	*
70	* @return a new NFA representing the conjunction of the specified NFA
71	*/
72	public static <I> CompactNFA<I> and(NFA<?, I> nfa1, NFA<?, I> nfa2, Alphabet<I> inputAlphabet) {
73	return and(nfa1, nfa2, inputAlphabet, new CompactNFA<>(inputAlphabet));	2✔
74	}
75
76	/**
77	* Calculates the conjunction ("and") of two NFAs via product construction and stores the result in a given mutable
78	* NFA.
79	*
80	* @param nfa1
81	* the first NFA
82	* @param nfa2
83	* the second NFA
84	* @param inputs
85	* the input symbols to consider
86	* @param out
87	* a mutable NFA for storing the result
88	* @param <I>
89	* input symbol type
90	* @param <S>
91	* state type
92	* @param <A>
93	* automaton type
94	*
95	* @return {@code out}, for convenience
96	*/
97	public static <I, S, A extends MutableNFA<S, I>> A and(NFA<?, I> nfa1,
98	NFA<?, I> nfa2,
99	Collection<? extends I> inputs,
100	A out) {
101	AcceptorTS<?, I> acc = Acceptors.combine(nfa1, nfa2, AcceptanceCombiner.AND);	2✔
102
103	TSCopy.copy(TSTraversalMethod.DEPTH_FIRST, acc, TSTraversal.NO_LIMIT, inputs, out);	2✔
104	return out;	2✔
105	}
106
107	/**
108	* Calculates the disjunction ("or") of two NFAs by merging their states and transitions. Returns the result as a
109	* new NFA.
110	*
111	* @param nfa1
112	* the first NFA
113	* @param nfa2
114	* the second NFA
115	* @param inputAlphabet
116	* the input alphabet
117	* @param <I>
118	* input symbol type
119	*
120	* @return a new NFA representing the conjunction of the specified NFA
121	*/
122	public static <I> CompactNFA<I> or(NFA<?, I> nfa1, NFA<?, I> nfa2, Alphabet<I> inputAlphabet) {
123	return or(nfa1, nfa2, inputAlphabet, new CompactNFA<>(inputAlphabet));	2✔
124	}
125
126	/**
127	* Calculates the disjunction ("or") of two NFAs by merging their states and transitions. Stores the result in a
128	* given mutable NFA.
129	*
130	* @param nfa1
131	* the first NFA
132	* @param nfa2
133	* the second NFA
134	* @param inputs
135	* the input symbols to consider
136	* @param out
137	* a mutable NFA for storing the result
138	* @param <I>
139	* input symbol type
140	* @param <S>
141	* state type
142	* @param <A>
143	* automaton type
144	*
145	* @return {@code out}, for convenience
146	*/
147	public static <I, S, A extends MutableNFA<S, I>> A or(NFA<?, I> nfa1,
148	NFA<?, I> nfa2,
149	Collection<? extends I> inputs,
150	A out) {
151	MutableNFAs.or(out, nfa1, inputs);	2✔
152	MutableNFAs.or(out, nfa2, inputs);	2✔
153
154	return out;	2✔
155	}
156
157	/**
158	* Creates an NFA for the reverse language of the given input NFA.
159	*
160	* @param nfa
161	* the input NFA
162	* @param inputAlphabet
163	* the input alphabet
164	* @param <I>
165	* input symbol type
166	*
167	* @return the reversed NFA
168	*/
169	public static <I> CompactNFA<I> reverse(NFA<?, I> nfa, Alphabet<I> inputAlphabet) {
170	final CompactNFA<I> result = new CompactNFA<>(inputAlphabet, nfa.size());	2✔
171	reverse(nfa, inputAlphabet, result);	2✔
172	return result;	2✔
173	}
174
175	/**
176	* Writes an NFA for the reverse language of the given input NFA into the given output NFA.
177	*
178	* @param nfa
179	* the input NFA
180	* @param inputs
181	* the input symbols to consider
182	* @param out
183	* the output NFA
184	* @param <SI>
185	* (input) state type
186	* @param <I>
187	* input symbol type
188	* @param <SO>
189	* (output) state type
190	* @param <A>
191	* (output) automaton type
192	*
193	* @return a mapping from output states to their original input states
194	*/
195	public static <SI, I, SO, A extends MutableNFA<SO, I>> Mapping<SO, SI> reverse(NFA<SI, I> nfa,
196	Collection<? extends I> inputs,
197	A out) {
198	final Set<SI> initialStates = nfa.getInitialStates();	2✔
199	final MutableMapping<SI, SO> mapping = nfa.createStaticStateMapping();	2✔
200	final MutableMapping<SO, SI> reverseMapping = out.createDynamicStateMapping();	2✔
201
202	// accepting states are initial states and vice versa
203	for (SI si : nfa) {	2✔
204	final SO so = out.addState(initialStates.contains(si));	2✔
205	out.setInitial(so, nfa.isAccepting(si));	2✔
206	mapping.put(si, so);	2✔
207	reverseMapping.put(so, si);	2✔
208	}	2✔
209
210	// reverse transitions
211	for (SI s1 : nfa) {	2✔
212	for (I a : inputs) {	2✔
213	for (SI s2 : nfa.getTransitions(s1, a)) {	2✔
214	out.addTransition(mapping.get(s2), a, mapping.get(s1));	2✔
215	}	2✔
216	}	2✔
217	}	2✔
218
219	return reverseMapping;	2✔
220	}
221
222	/**
223	* Creates a trim NFA from the given input NFA. An NFA is trim if all of its states are accessible and
224	* co-accessible.
225	*
226	* @param nfa
227	* the input NFA
228	* @param inputAlphabet
229	* the input alphabet
230	* @param <I>
231	* input symbol type
232	*
233	* @return the trim NFA
234	*
235	* @see #accessibleStates(NFA, Collection)
236	* @see #coaccessibleStates(NFA, Collection)
237	*/
238	public static <I> CompactNFA<I> trim(NFA<?, I> nfa, Alphabet<I> inputAlphabet) {
239	return trim(nfa, inputAlphabet, new CompactNFA<>(inputAlphabet));	2✔
240	}
241
242	/**
243	* Creates a trim NFA from the given input NFA and writes it to the given output NFA. An NFA is trim if all of its
244	* states are accessible and co-accessible.
245	*
246	* @param nfa
247	* the input NFA
248	* @param inputs
249	* the input symbols to consider
250	* @param out
251	* the output NFA
252	* @param <SI>
253	* (input) state type
254	* @param <I>
255	* input symbol type
256	* @param <SO>
257	* (output) state type
258	* @param <A>
259	* (output) automaton type
260	*
261	* @return {@code out} for convenience
262	*
263	* @see #accessibleStates(NFA, Collection)
264	* @see #coaccessibleStates(NFA, Collection)
265	*/
266	public static <SI, I, SO, A extends MutableNFA<SO, I>> A trim(NFA<SI, I> nfa,
267	Collection<? extends I> inputs,
268	A out) {
269	final MutableMapping<SI, SO> mapping = nfa.createStaticStateMapping();	2✔
270	final Set<SI> inits = nfa.getInitialStates();	2✔
271
272	final Set<SI> states = accessibleStates(nfa, inputs);	2✔
273	states.retainAll(coaccessibleStates(nfa, inputs));	2✔
274
275	for (SI s : states) {	2✔
276	final SO so = out.addState(nfa.isAccepting(s));	2✔
277	out.setInitial(so, inits.contains(s));	2✔
278	mapping.put(s, so);	2✔
279	}	2✔
280
281	for (SI s : states) {	2✔
282	for (I i : inputs) {	2✔
283	for (SI t : nfa.getTransitions(s, i)) {	2✔
284	if (states.contains(t)) {	2✔
285	out.addTransition(mapping.get(s), i, mapping.get(t));	2✔
286	}
287	}	2✔
288	}	2✔
289	}	2✔
290
291	return out;	2✔
292	}
293
294	/**
295	* Returns for a given NFA the set of accessible states. A state is accessible if it can be reached by an initial
296	* state.
297	*
298	* @param nfa
299	* the input NFA
300	* @param inputs
301	* the input symbols to consider
302	* @param <S>
303	* state type
304	* @param <I>
305	* input symbol type
306	*
307	* @return the set of accessible states
308	*/
309	public static <S, I> Set<S> accessibleStates(NFA<S, I> nfa, Collection<? extends I> inputs) {
310
311	final Set<S> inits = nfa.getInitialStates();	2✔
312	final Deque<S> deque = new ArrayDeque<>(inits);	2✔
313	final Set<S> found = new HashSet<>(inits);	2✔
314
315	while (!deque.isEmpty()) {	2✔
316	final S curr = deque.pop();	2✔
317	for (I sym : inputs) {	2✔
318	for (S succ : nfa.getSuccessors(curr, sym)) {	2✔
319	if (found.add(succ)) {	2✔
320	deque.push(succ);	2✔
321	}
322	}	2✔
323	}	2✔
324	}	2✔
325
326	return found;	2✔
327	}
328
329	/**
330	* Returns for a given NFA the set of co-accessible states. A state is co-accessible if it reaches an accepting
331	* state.
332	*
333	* @param nfa
334	* the input NFA
335	* @param inputs
336	* the input symbols to consider
337	* @param <S>
338	* state type
339	* @param <I>
340	* input symbol type
341	*
342	* @return the set of co-accessible states
343	*/
344	public static <S, I> Set<S> coaccessibleStates(NFA<S, I> nfa, Collection<? extends I> inputs) {
345
346	final CompactNFA<I> out = new CompactNFA<>(new MapAlphabet<>(inputs), nfa.size());	2✔
347	final Mapping<Integer, S> mapping = reverse(nfa, inputs, out);	2✔
348	final Set<Integer> states = accessibleStates(out, inputs);	2✔
349
350	final Set<S> result = new HashSet<>(HashUtil.capacity(states.size()));	2✔
351
352	for (Integer s : states) {	2✔
353	result.add(mapping.get(s));	2✔
354	}	2✔
355
356	return result;	2✔
357	}
358
359	/**
360	* Determinizes the given NFA, and returns the result as a new complete DFA.
361	*
362	* @param nfa
363	* the original NFA
364	* @param inputAlphabet
365	* the input alphabet
366	* @param <I>
367	* input symbol type
368	*
369	* @return the determinized NFA
370	*/
371	public static <I> CompactDFA<I> determinize(NFA<?, I> nfa, Alphabet<I> inputAlphabet) {
372	return determinize(nfa, inputAlphabet, false, true);	2✔
373	}
374
375	/**
376	* Determinizes the given NFA, and returns the result as a new DFA.
377	*
378	* @param nfa
379	* the original NFA
380	* @param inputAlphabet
381	* the input alphabet
382	* @param partial
383	* allows the new DFA to be partial
384	* @param minimize
385	* whether to minimize the DFA
386	* @param <I>
387	* input symbol type
388	*
389	* @return the determinized NFA
390	*/
391	public static <I> CompactDFA<I> determinize(NFA<?, I> nfa,
392	Alphabet<I> inputAlphabet,
393	boolean partial,
394	boolean minimize) {
395	CompactDFA<I> result = new CompactDFA<>(inputAlphabet);	2✔
396	determinize(nfa, inputAlphabet, result, partial, minimize);	2✔
397	return result;	2✔
398	}
399
400	/**
401	* Determinizes the given NFA, and stores the result in a given mutable DFA.
402	*
403	* @param nfa
404	* the original NFA
405	* @param inputs
406	* the input symbols to consider
407	* @param out
408	* a mutable DFA for storing the result
409	* @param partial
410	* allows the new DFA to be partial
411	* @param minimize
412	* whether to minimize the DFA
413	* @param <I>
414	* input symbol type
415	*/
416	public static <I> void determinize(NFA<?, I> nfa,
417	Collection<? extends I> inputs,
418	MutableDFA<?, I> out,
419	boolean partial,
420	boolean minimize) {
421	doDeterminize(nfa.powersetView(), inputs, out, partial);	2✔
422	if (minimize) {	2✔
423	HopcroftMinimizer.minimizeDFAInvasive(out, inputs);	2✔
424	}
425	}	2✔
426
427	/**
428	* Determinizes the given NFA, and returns the result as a new DFA.
429	*
430	* @param nfa
431	* the original NFA
432	* @param <I>
433	* input symbol type
434	* @param <A>
435	* automaton type
436	*
437	* @return the determinized NFA
438	*/
439	public static <I, A extends NFA<?, I> & InputAlphabetHolder<I>> CompactDFA<I> determinize(A nfa) {
440	return determinize(nfa, false, true);	2✔
441	}
442
443	/**
444	* Determinizes the given NFA, and returns the result as a new DFA.
445	*
446	* @param nfa
447	* the original NFA
448	* @param partial
449	* allows the new DFA to be partial
450	* @param minimize
451	* whether to minimize the DFA
452	* @param <I>
453	* input symbol type
454	* @param <A>
455	* automaton type
456	*
457	* @return the determinized NFA
458	*/
459	public static <I, A extends NFA<?, I> & InputAlphabetHolder<I>> CompactDFA<I> determinize(A nfa,
460	boolean partial,
461	boolean minimize) {
462	return determinize(nfa, nfa.getInputAlphabet(), partial, minimize);	2✔
463	}
464
465	/**
466	* Determinizes the given NFA, and stores the result in a given mutable DFA.
467	*
468	* @param nfa
469	* the original NFA
470	* @param inputs
471	* the input symbols to consider
472	* @param out
473	* a mutable DFA for storing the result
474	* @param <I>
475	* input symbol type
476	*/
477	public static <I> void determinize(NFA<?, I> nfa, Collection<? extends I> inputs, MutableDFA<?, I> out) {
478	determinize(nfa, inputs, out, false, true);	×
479	}	×
480
481	private static <I, SI, SO> void doDeterminize(AcceptorPowersetViewTS<SI, I, ?> powerset,
482	Collection<? extends I> inputs,
483	MutableDFA<SO, I> out,
484	boolean partial) {
485	Map<SI, SO> outStateMap = new HashMap<>();	2✔
486	Deque<DeterminizeRecord<SI, SO>> stack = new ArrayDeque<>();	2✔
487
488	final SI init = powerset.getInitialState();	2✔
489
490	if (init == null) {	2✔
NEW 491	return;	×
492	}
493
494	final boolean initAcc = powerset.isAccepting(init);	2✔
495	final SO initOut = out.addInitialState(initAcc);	2✔
496
497	outStateMap.put(init, initOut);	2✔
498
499	stack.push(new DeterminizeRecord<>(init, initOut));	2✔
500
501	while (!stack.isEmpty()) {	2✔
502	DeterminizeRecord<SI, SO> curr = stack.pop();	2✔
503
504	SI inState = curr.inputState;	2✔
505	SO outState = curr.outputState;	2✔
506
507	for (I sym : inputs) {	2✔
508	final SI succ = powerset.getSuccessor(inState, sym);	2✔
509
510	if (succ != null) {	2✔
511	SO outSucc = outStateMap.get(succ);	2✔
512	if (outSucc == null) {	2✔
513	// add new state to DFA and to stack
514	outSucc = out.addState(powerset.isAccepting(succ));	2✔
515	outStateMap.put(succ, outSucc);	2✔
516	stack.push(new DeterminizeRecord<>(succ, outSucc));	2✔
517	}
518	out.setTransition(outState, sym, outSucc);	2✔
519	} else if (!partial) {	2✔
NEW 520	throw new IllegalStateException("Cannot create a total DFA from a partial powerset view");	×
521	}
522	}	2✔
523	}	2✔
524	}	2✔
525
526	private static final class DeterminizeRecord<SI, SO> {
527
528	private final SI inputState;
529	private final SO outputState;
530
531	DeterminizeRecord(SI inputState, SO outputState) {	2✔
532	this.inputState = inputState;	2✔
533	this.outputState = outputState;	2✔
534	}	2✔
535	}
536	}

LearnLib / automatalib / 12651580329

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