Compiler Design
Finite Automata & DFA Construction / DFA Minimization
Converting an NFA to a DFA can yield a machine with redundant states. **DFA Minimization** reduces the number of states to the absolute mathematical minimum while preserving the same language acceptance.
Myhill-Nerode Partitioning Algorithm
The algorithm works by splitting the set of all DFA states into partitions of equivalent states. Equivalent states are those that behave identically under all possible inputs.
1. Partition all states into two groups:
- Group 1: All ACCEPT states (F)
- Group 2: All NON-ACCEPT states (S - F)
Let the initial partition be P = {F, S - F}.
2. Loop:
For each group G in partition P:
Split G into subgroups such that two states s and t in G
remain in the same subgroup if and only if:
For all input symbols 'a':
s and t transition to states in the same partition group.
(i.e., trans(s, 'a') and trans(t, 'a') belong to the same group in P)
If P changes (new split occurs):
Update P and repeat the loop.
Else:
Stop. The current partition groups represent the minimized states.
3. Merge all equivalent states in each group into a single state.Distinguishable vs Equivalent States
Two states s and t are distinguishable if there is some string w such that transitioning on w from s leads to an accept state, while transitioning on w from t leads to a non-accept state (or vice-versa).