public 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, an explicit sink must be inserted. This is done on-the-fly
when using one of the minimizePartial...
methods. If any other 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.
|
Constructor and Description |
---|
HopcroftMinimization() |
Modifier and Type | Method and Description |
---|---|
static <I,A extends DFA<?,I> & InputAlphabetHolder<I>> |
minimizeDFA(A dfa)
Minimizes the given DFA.
|
static <I,A extends DFA<?,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 <I,O,A extends MealyMachine<?,I,?,O> & InputAlphabetHolder<I>> |
minimizeMealy(A mealy)
Minimizes the given Mealy machine.
|
static <I,O,A extends MealyMachine<?,I,?,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.
|
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 <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,A extends MealyMachine<?,I,?,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,A extends MealyMachine<?,I,?,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 <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 <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,A extends DFA<?,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,A extends DFA<?,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 minimizeCopyright © 2015. All rights reserved.