12651127735

Committed 07 Jan 2025 12:00PM UTC coverage: 91.569%. First build

Build # 12651127735

Build Type

Pull #85

github

Committed by

web-flow

Commit Message

Merge 65592992c into d156e0830

Pull Request Pull Request #85: Update dependencies

Run Details

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

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 / 12651127735

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