public final class HopcroftMinimization extends Object
Hopcroft's algorithm is a special case of the Paige/Tarjan partition refinement algorithm (see PaigeTarjan
)
for the case of deterministic automata. Its running time is O(nk log n)
, where n
is the size of the
input DFA and k
the size of the input alphabet.
Important note: Hopcroft's minimization algorithm works for complete automata only. If the automaton is
partial, please use PaigeTarjanMinimization
instead. If any method is invoked with a partial automaton as its
argument, this will result in a IllegalArgumentException
at runtime.
Note that the partition refinement step only calculates classes of equivalent states. However, minimization also
requires pruning of states that cannot be reached from the initial states. Most methods in this class have a variable
called pruningMode
of type HopcroftMinimization.PruningMode
that controls if and when pruning is performed: if the
automaton to be minimized is known to be initially connected (i.e., it contains no unreachable states),
pruning can be omitted completely (by specifying HopcroftMinimization.PruningMode.DONT_PRUNE
) without impairing correctness.
Otherwise, pruning can be chosen to be performed on the automaton to be minimized (HopcroftMinimization.PruningMode.PRUNE_BEFORE
),
or on the calculated state partition (HopcroftMinimization.PruningMode.PRUNE_AFTER
). For methods that do not provide a pruningMode
parameter, the default is HopcroftMinimization.PruningMode.PRUNE_AFTER
.
Modifier and Type | Class and Description |
---|---|
static class |
HopcroftMinimization.PruningMode
Allows for controlling how automata are pruned during minimization.
|
Modifier and Type | Method and Description |
---|---|
static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> |
minimizeDFA(A dfa)
Minimizes the given DFA.
|
static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> |
minimizeDFA(A dfa,
HopcroftMinimization.PruningMode pruningMode)
Minimizes the given DFA.
|
static <I> CompactDFA<I> |
minimizeDFA(DFA<?,I> dfa,
Alphabet<I> alphabet)
Minimizes the given DFA.
|
static <I> CompactDFA<I> |
minimizeDFA(DFA<?,I> dfa,
Alphabet<I> alphabet,
HopcroftMinimization.PruningMode pruningMode)
Minimizes the given DFA.
|
static <A extends MutableDFA<?,I>,I> |
minimizeDFA(DFA<?,I> dfa,
Alphabet<I> alphabet,
HopcroftMinimization.PruningMode pruningMode,
AutomatonCreator<A,I> creator)
Minimizes the given DFA.
|
static <S,I,T,O,A extends MealyMachine<S,I,T,O> & InputAlphabetHolder<I>> |
minimizeMealy(A mealy)
Minimizes the given Mealy machine.
|
static <S,I,T,O,A extends MealyMachine<S,I,T,O> & InputAlphabetHolder<I>> |
minimizeMealy(A mealy,
HopcroftMinimization.PruningMode pruningMode)
Minimizes the given Mealy machine.
|
static <I,O> CompactMealy<I,O> |
minimizeMealy(MealyMachine<?,I,?,O> mealy,
Alphabet<I> alphabet)
Minimizes the given Mealy machine.
|
static <I,O> CompactMealy<I,O> |
minimizeMealy(MealyMachine<?,I,?,O> mealy,
Alphabet<I> alphabet,
HopcroftMinimization.PruningMode pruningMode)
Minimizes the given Mealy machine.
|
static <A extends MutableMealyMachine<?,I,?,O>,I,O> |
minimizeMealy(MealyMachine<?,I,?,O> mealy,
Alphabet<I> alphabet,
HopcroftMinimization.PruningMode pruningMode,
AutomatonCreator<A,I> creator)
Minimizes the given Mealy machine.
|
static <I,T,SP,TP,A extends MutableDeterministic<?,I,?,SP,TP>> |
minimizeUniversal(UniversalDeterministicAutomaton<?,I,T,SP,TP> automaton,
Alphabet<I> alphabet,
AutomatonCreator<A,I> creator,
AutomatonInitialPartitioning ap,
HopcroftMinimization.PruningMode pruningMode)
Minimizes the given automaton depending on the given partitioning function.
|
public static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> CompactDFA<I> minimizeDFA(A dfa)
CompactDFA
, using the input alphabet
obtained via dfa.getInputAlphabet()
. Pruning (see
above) is performed after computing state equivalences.dfa
- the DFA to minimizepublic static <S,I,A extends DFA<S,I> & InputAlphabetHolder<I>> CompactDFA<I> minimizeDFA(A dfa, HopcroftMinimization.PruningMode pruningMode)
CompactDFA
, using the input alphabet
obtained via dfa.getInputAlphabet()
.dfa
- the DFA to minimizepruningMode
- the pruning mode (see above)public static <I> CompactDFA<I> minimizeDFA(DFA<?,I> dfa, Alphabet<I> alphabet)
CompactDFA
, and pruning (see above) is
performed after computing state equivalences.dfa
- the DFA to minimizealphabet
- the input alphabet (this will be the input alphabet of the returned DFA)public static <I> CompactDFA<I> minimizeDFA(DFA<?,I> dfa, Alphabet<I> alphabet, HopcroftMinimization.PruningMode pruningMode)
CompactDFA
.dfa
- the DFA to minimizealphabet
- the input alphabet (this will be the input alphabet of the returned DFA)pruningMode
- the pruning mode (see above)public static <A extends MutableDFA<?,I>,I> A minimizeDFA(DFA<?,I> dfa, Alphabet<I> alphabet, HopcroftMinimization.PruningMode pruningMode, AutomatonCreator<A,I> creator)
CompactDFA
.dfa
- the DFA to minimizealphabet
- the input alphabet (this will be the input alphabet of the returned DFA)pruningMode
- the pruning mode (see above)creator
- the creator for constructing the automata instance to returnpublic static <S,I,T,O,A extends MealyMachine<S,I,T,O> & InputAlphabetHolder<I>> CompactMealy<I,O> minimizeMealy(A mealy)
CompactMealy
, using the
alphabet obtained via mealy.getInputAlphabet()
.
Pruning (see above) is performed after computing state equivalences.mealy
- the Mealy machine to minimizepublic static <S,I,T,O,A extends MealyMachine<S,I,T,O> & InputAlphabetHolder<I>> CompactMealy<I,O> minimizeMealy(A mealy, HopcroftMinimization.PruningMode pruningMode)
CompactMealy
, using the
alphabet obtained via mealy.getInputAlphabet()
.mealy
- the Mealy machine to minimizepruningMode
- the pruning mode (see above)public static <I,O> CompactMealy<I,O> minimizeMealy(MealyMachine<?,I,?,O> mealy, Alphabet<I> alphabet)
CompactMealy
, and pruning (see
above) is performed after computing state equivalences.mealy
- the Mealy machine to minimizealphabet
- the input alphabet (this will be the input alphabet of the resulting Mealy machine)public static <I,O> CompactMealy<I,O> minimizeMealy(MealyMachine<?,I,?,O> mealy, Alphabet<I> alphabet, HopcroftMinimization.PruningMode pruningMode)
CompactMealy
.mealy
- the Mealy machine to minimizealphabet
- the input alphabet (this will be the input alphabet of the resulting Mealy machine)pruningMode
- the pruning mode (see above)public static <A extends MutableMealyMachine<?,I,?,O>,I,O> A minimizeMealy(MealyMachine<?,I,?,O> mealy, Alphabet<I> alphabet, HopcroftMinimization.PruningMode pruningMode, AutomatonCreator<A,I> creator)
CompactMealy
.mealy
- the Mealy machine to minimizealphabet
- the input alphabet (this will be the input alphabet of the resulting Mealy machine)pruningMode
- the pruning mode (see above)creator
- the creator for constructing the automata instance to returnpublic static <I,T,SP,TP,A extends MutableDeterministic<?,I,?,SP,TP>> A minimizeUniversal(UniversalDeterministicAutomaton<?,I,T,SP,TP> automaton, Alphabet<I> alphabet, AutomatonCreator<A,I> creator, AutomatonInitialPartitioning ap, HopcroftMinimization.PruningMode pruningMode)
automaton
- the automaton to minimizealphabet
- the input alphabet (this will be the input alphabet of the resulting Mealy machine)creator
- the creator for constructing the automata instance to returnap
- the initial partitioning function, determining how states will be distinguishedpruningMode
- the pruning mode (see above)creator
.AutomatonInitialPartitioning
Copyright © 2020. All rights reserved.