DFA Minimization Visualizer

📘 DFA Minimization

DFA Minimization is a core concept in Theory of Computation that transforms a given DFA into its canonical (unique minimal form) without changing the language it recognizes.

It ensures that no two states are equivalent, meaning every state is distinguishable by at least one input string.

The minimized DFA is optimal — it has the least number of states possible for that language.

🎯 Why Minimization?

• Efficiency: Fewer states → faster computation & less memory
• Canonical Form: Unique representation of a regular language
• Optimization: Removes redundant & duplicate states
• Real-world Use: Used in compilers, regex engines & digital circuits

⚙️ Myhill–Nerode Theorem

This theorem defines an equivalence relation on strings:

Two states are equivalent if no string can distinguish them.

• Mark distinguishable state pairs
• Propagate markings using transitions
• Unmarked pairs → equivalent → merge

This forms the theoretical foundation of DFA minimization.

⚡Partition Refinement

The most efficient DFA minimization algorithm based on partition refinement.

• Start with {Final, Non-Final} partition
• Split states based on transitions
• Repeat until partitions stabilize

Time Complexity: O(n log n) (optimal)