21247581665

Committed 22 Jan 2026 11:58AM UTC coverage: 92.937% (+0.003%) from 92.934%

Build # 21247581665

Build Type

push

github

Committed by

mtf90

Commit Message

NFAs: add Brzozowski's algorithm

Coverage Stats

10 of 12 new or added lines in 1 file covered. (83.33%)

17449 of 18775 relevant lines covered (92.94%)

1.72 hits per line

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

96.69

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

/* Copyright (C) 2013-2026 TU Dortmund University
 * This file is part of AutomataLib <https://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.AutomatonCreator;
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;
    }

    /**
     * Canonizes the given NFA using <a
     * href="https://en.wikipedia.org/wiki/DFA_minimization#Brzozowski's_algorithm">Brzozowski's algorithm</a>.
     *
     * @param nfa
     *         the original NFA
     * @param <I>
     *         input symbol type
     * @param <A>
     *         automaton type
     *
     * @return the canonized NFA
     *
     * @see #determinize(NFA)
     */
    public static <I, A extends NFA<?, I> & InputAlphabetHolder<I>> CompactDFA<I> canonize(A nfa) {
        return canonize(nfa, nfa.getInputAlphabet());
    }

    /**
     * Canonizes the given NFA using <a
     * href="https://en.wikipedia.org/wiki/DFA_minimization#Brzozowski's_algorithm">Brzozowski's algorithm</a>.
     *
     * @param nfa
     *         the original NFA
     * @param alphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return the canonized NFA
     *
     * @see #determinize(NFA, Alphabet)
     */
    public static <I> CompactDFA<I> canonize(NFA<?, I> nfa, Alphabet<I> alphabet) {
        return canonize(nfa, alphabet, new CompactDFA.Creator<>());
    }

    /**
     * Canonizes the given NFA using <a
     * href="https://en.wikipedia.org/wiki/DFA_minimization#Brzozowski's_algorithm">Brzozowski's algorithm</a>.
     *
     * @param nfa
     *         the original NFA
     * @param alphabet
     *         the input alphabet
     * @param creator
     *         the creator for the intermediate and final DFAs
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <A>
     *         automaton type
     *
     * @return the canonized NFA
     *
     * @see #determinize(NFA, Alphabet)
     */
    public static <S, I, A extends MutableDFA<S, I>> A canonize(NFA<?, I> nfa,
                                                                Alphabet<I> alphabet,
                                                                AutomatonCreator<A, I> creator) {
        return canonize(nfa, alphabet, creator.createAutomaton(alphabet), new CompactNFA<>(alphabet));
    }

    /**
     * Canonizes the given NFA using <a
     * href="https://en.wikipedia.org/wiki/DFA_minimization#Brzozowski's_algorithm">Brzozowski's algorithm</a>.
     *
     * @param nfa
     *         the original NFA
     * @param inputs
     *         the input symbols to consider
     * @param dfaOut
     *         the instance to write intermediate and final DFAs to
     * @param nfaOut
     *         the instance to write intermediate NFAs to
     * @param <S1>
     *         DFA state type
     * @param <S2>
     *         NFA state type
     * @param <I>
     *         input symbol type
     * @param <A1>
     *         DFA automaton type
     * @param <A2>
     *         NFA automaton type
     *
     * @return the canonized NFA
     *
     * @see #determinize(NFA, Alphabet)
     */
    public static <S1, S2, I, A1 extends MutableDFA<S1, I>, A2 extends MutableNFA<S2, I>> A1 canonize(NFA<?, I> nfa,
                                                                                                      Collection<? extends I> inputs,
                                                                                                      A1 dfaOut,
                                                                                                      A2 nfaOut) {
        reverse(nfa, inputs, nfaOut);
        determinize(nfaOut, inputs, dfaOut, false, false);

        nfaOut.clear();

        reverse(dfaOut, inputs, nfaOut);

        dfaOut.clear();

        determinize(nfaOut, inputs, dfaOut, false, false);

        return dfaOut;
    }

    /**
     * Determinizes the given NFA using <a href="https://doi.org/10.1147/rd.32.0114">subset construction</a> and
     * minimizes the result afterward.
     *
     * @param nfa
     *         the original NFA
     * @param inputAlphabet
     *         the input alphabet
     * @param <I>
     *         input symbol type
     *
     * @return the determinized NFA
     *
     * @see #canonize(NFA, Alphabet)
     */
    public static <I> CompactDFA<I> determinize(NFA<?, I> nfa, Alphabet<I> inputAlphabet) {
        return determinize(nfa, inputAlphabet, false, true);
    }

    /**
     * Determinizes the given NFA using <a href="https://doi.org/10.1147/rd.32.0114">subset construction</a>, optionally
     * minimizing the result afterward.
     *
     * @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
     *
     * @see #canonize(NFA, Alphabet)
     */
    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 using <a href="https://doi.org/10.1147/rd.32.0114">subset construction</a>, optionally
     * minimizing the result afterward.
     *
     * @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
     *
     * @see #canonize(NFA, Alphabet, AutomatonCreator)
     */
    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 using <a href="https://doi.org/10.1147/rd.32.0114">subset construction</a> and
     * minimizes the result afterward.
     *
     * @param nfa
     *         the original NFA
     * @param <I>
     *         input symbol type
     * @param <A>
     *         automaton type
     *
     * @return the determinized NFA
     *
     * @see #canonize(NFA)
     */
    public static <I, A extends NFA<?, I> & InputAlphabetHolder<I>> CompactDFA<I> determinize(A nfa) {
        return determinize(nfa, false, true);
    }

    /**
     * Determinizes the given NFA using <a href="https://doi.org/10.1147/rd.32.0114">subset construction</a> and
     * minimizes the result afterward.
     *
     * @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
     *
     * @see #canonize(NFA, Alphabet, AutomatonCreator)
     */
    public static <I> void determinize(NFA<?, I> nfa, Collection<? extends I> inputs, MutableDFA<?, I> out) {
        determinize(nfa, inputs, out, false, true);
    }

    /**
     * Determinizes the given NFA using <a href="https://doi.org/10.1147/rd.32.0114">subset construction</a>, optionally
     * minimizing the result afterward.
     *
     * @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
     *
     * @see #canonize(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);
    }

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

LearnLib / automatalib / 21247581665

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