How to use the DFA Minimization Tool
- 1. Paste the tableFirst line has the input symbols. Each next line has a state and its next state for each symbol.
- 2. Mark start and finalsPut -> before the start state and * before each final state. Use - for a missing move.
- 3. Read the partitionsSee each refinement round with group numbers, then the minimised DFA.
How DFA minimisation works
Two states are equivalent if, for every input string, both lead to acceptance or both lead to rejection. Minimisation merges equivalent states. The method taught in most syllabi is partition refinement (k-equivalence):
- Remove states that cannot be reached from the start state.
- P0 has two groups: non-final states and final states.
- To build Pk+1, split each group so that two states stay together only if, on every symbol, they go to states in the same group of Pk.
- Stop when a round splits nothing. Each group becomes one state of the minimal DFA.
If a move is missing, the tool adds a dead state ∅ first, because the algorithm needs a complete DFA.
Worked example
This DFA over {a, b} has states A to E, with A the start and E final. A → (B, C), B → (B, D), C → (B, C), D → (B, E) and E → (B, C). These are the tool's default values.
- P0 = {A, B, C, D} {E}.
- On b, D goes to the final group but A, B and C do not. So P1 = {A, B, C} {D} {E}.
- On b, B goes to D but A and C go to C. So P2 = {A, C} {B} {D} {E}.
- P3 makes no change, so A and C merge. The minimal DFA has 4 states.
This DFA accepts strings ending in abb. It is the subset-construction output for (a|b)*abb in the Aho, Lam, Sethi and Ullman compiler book.
Tips for exam answers
Always remove unreachable states first, otherwise your count can be wrong. Write each partition on its own line. The minimal DFA is unique up to state names, so a different grouping order still gives the same number of states. The table-filling (Myhill-Nerode) method gives the same answer. To test strings on the result, use the DFA simulator. To build a DFA from an NFA first, use the NFA to DFA converter.
Frequently asked questions
What input format does the tool accept?
A header line with symbols, then lines like ->A B C or *E B C. Each line gives the state and its next state for each symbol in header order.
What if my DFA has a missing transition?
Type - in that cell. The tool adds a dead state ∅ that loops to itself, which is the standard way to complete a DFA.
Does it use the table-filling method?
It uses partition refinement (k-equivalence). Table filling marks distinguishable pairs instead, but both methods give the same minimal DFA.
Can the minimal DFA have only one state?
Yes. If every reachable state is final, or none is, all states are equivalent and merge into one.