Package dk.brics.automaton
Class MinimizationOperations
- java.lang.Object
-
- dk.brics.automaton.MinimizationOperations
-
public final class MinimizationOperations extends java.lang.Object
Operations for minimizing automata.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
MinimizationOperations.IntPair
(package private) static class
MinimizationOperations.LabelComparator
(package private) static class
MinimizationOperations.Partition
(package private) static class
MinimizationOperations.StateList
(package private) static class
MinimizationOperations.StateListNode
-
Constructor Summary
Constructors Modifier Constructor Description private
MinimizationOperations()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description private static void
addTriggers(Transition[][] transitions, java.util.ArrayList<java.util.ArrayList<java.util.HashSet<MinimizationOperations.IntPair>>> triggers, int n1, int n2)
private static <T> void
initialize(java.util.ArrayList<T> list, int size)
private static void
makeAdjacent(int[] A, int[] F, int[] K, int nn, int mm)
private static void
markPair(boolean[][] mark, java.util.ArrayList<java.util.ArrayList<java.util.HashSet<MinimizationOperations.IntPair>>> triggers, int n1, int n2)
static void
minimize(Automaton a)
Minimizes (and determinizes if not already deterministic) the given automaton.static void
minimizeBrzozowski(Automaton a)
Minimizes the given automaton using Brzozowski's algorithm.static void
minimizeHopcroft(Automaton a)
Minimizes the given automaton using Hopcroft's algorithm.static void
minimizeHuffman(Automaton a)
Minimizes the given automaton using Huffman's algorithm.static void
minimizeValmari(Automaton automaton)
Minimizes the given automaton using Valmari's algorithm.private static void
splitTransitions(java.util.Set<State> states)
private static boolean
statesAgree(Transition[][] transitions, boolean[][] mark, int n1, int n2)
-
-
-
Method Detail
-
minimize
public static void minimize(Automaton a)
Minimizes (and determinizes if not already deterministic) the given automaton.- See Also:
Automaton.setMinimization(int)
-
statesAgree
private static boolean statesAgree(Transition[][] transitions, boolean[][] mark, int n1, int n2)
-
addTriggers
private static void addTriggers(Transition[][] transitions, java.util.ArrayList<java.util.ArrayList<java.util.HashSet<MinimizationOperations.IntPair>>> triggers, int n1, int n2)
-
markPair
private static void markPair(boolean[][] mark, java.util.ArrayList<java.util.ArrayList<java.util.HashSet<MinimizationOperations.IntPair>>> triggers, int n1, int n2)
-
initialize
private static <T> void initialize(java.util.ArrayList<T> list, int size)
-
minimizeHuffman
public static void minimizeHuffman(Automaton a)
Minimizes the given automaton using Huffman's algorithm.
-
minimizeBrzozowski
public static void minimizeBrzozowski(Automaton a)
Minimizes the given automaton using Brzozowski's algorithm.
-
minimizeHopcroft
public static void minimizeHopcroft(Automaton a)
Minimizes the given automaton using Hopcroft's algorithm.
-
minimizeValmari
public static void minimizeValmari(Automaton automaton)
Minimizes the given automaton using Valmari's algorithm.
-
makeAdjacent
private static void makeAdjacent(int[] A, int[] F, int[] K, int nn, int mm)
-
splitTransitions
private static void splitTransitions(java.util.Set<State> states)
-
-