DFA Minimization

Cheatsheet Content

DFA Minimization DFA minimization is the process of transforming a given DFA into an equivalent DFA that has the minimum number of states. This is useful for optimizing automata and reducing memory usage. Why Minimize? Reduces the number of states, simplifying the DFA. Optimizes memory usage and processing time. Every regular language has a unique minimal DFA. Algorithm: Table-Filling Method (Hopcroft's Algorithm Principle) This method identifies and merges equivalent states. Two states $p$ and $q$ are equivalent if, for all input symbols $a$, they transition to equivalent states, and both are either final or non-final states. Remove Unreachable States: Start from the initial state and perform a traversal (BFS or DFS) to find all reachable states. Any state not reachable from the initial state can be removed. Initialize Table: Create a table of all pairs of states $(q_i, q_j)$ where $i \neq j$. Mark a pair $(q_i, q_j)$ as distinguishable if one is a final state and the other is a non-final state. Iterate and Mark: Repeat until no new pairs can be marked: For each unmarked pair $(q_i, q_j)$ and for each input symbol $a$: Let $q'_i = \delta(q_i, a)$ and $q'_j = \delta(q_j, a)$. If the pair $(q'_i, q'_j)$ is marked as distinguishable, then mark $(q_i, q_j)$ as distinguishable. Construct Minimal DFA: All unmarked pairs $(q_i, q_j)$ are equivalent. Group these equivalent states into equivalence classes. Each equivalence class forms a single state in the minimized DFA. The initial state of the new DFA is the equivalence class containing the original initial state. A state (equivalence class) in the new DFA is a final state if it contains at least one original final state (if all states in an equivalence class are final, then the new state is final). Transitions: If $\delta(q_i, a) = q_k$, then for an equivalence class $C_p$ containing $q_i$, and $C_m$ containing $q_k$, the transition in the minimized DFA is $\delta(C_p, a) = C_m$. Example: Minimizing a DFA Original DFA States and Transitions: Let $Q = \{q_0, q_1, q_2, q_3, q_4, q_5\}$, $\Sigma = \{0, 1\}$, $q_0$ is initial, $F = \{q_2, q_4\}$. State $\delta(q, 0)$ $\delta(q, 1)$ $q_0$ $q_1$ $q_2$ $q_1$ $q_3$ $q_4$ $q_2$ $q_5$ $q_4$ $q_3$ $q_0$ $q_4$ $q_4$ $q_4$ $q_4$ $q_5$ $q_4$ $q_4$ Step 1: Remove Unreachable States All states are reachable from $q_0$. No states to remove. Step 2 & 3: Initialize and Iterate (Table-Filling) Mark distinguishable pairs. Final states: $\{q_2, q_4\}$. Non-final states: $\{q_0, q_1, q_3, q_5\}$. Initially, mark all pairs $(q_i, q_j)$ where one is final and the other is non-final. $(q_0, q_2), (q_0, q_4)$ marked $(q_1, q_2), (q_1, q_4)$ marked $(q_3, q_2), (q_3, q_4)$ marked $(q_5, q_2), (q_5, q_4)$ marked Iterate: Consider $(q_0, q_1)$: $\delta(q_0, 0)=q_1$, $\delta(q_1, 0)=q_3$. $(q_1, q_3)$ is unmarked. $\delta(q_0, 1)=q_2$, $\delta(q_1, 1)=q_4$. $(q_2, q_4)$ is unmarked (both final). $(q_0, q_1)$ remains unmarked. Consider $(q_0, q_3)$: $\delta(q_0, 0)=q_1$, $\delta(q_3, 0)=q_0$. $(q_1, q_0)$ is unmarked. $\delta(q_0, 1)=q_2$, $\delta(q_3, 1)=q_4$. $(q_2, q_4)$ is unmarked. $(q_0, q_3)$ remains unmarked. Consider $(q_0, q_5)$: $\delta(q_0, 0)=q_1$, $\delta(q_5, 0)=q_4$. $(q_1, q_4)$ is marked (non-final, final). So, mark $(q_0, q_5)$. Consider $(q_1, q_3)$: $\delta(q_1, 0)=q_3$, $\delta(q_3, 0)=q_0$. $(q_3, q_0)$ is unmarked. $\delta(q_1, 1)=q_4$, $\delta(q_3, 1)=q_4$. $(q_4, q_4)$ trivial. $(q_1, q_3)$ remains unmarked. Consider $(q_2, q_5)$: $\delta(q_2, 0)=q_5$, $\delta(q_5, 0)=q_4$. $(q_5, q_4)$ is marked (non-final, final). So, mark $(q_2, q_5)$. After iterations, the unmarked pairs are: $(q_0, q_1)$, $(q_0, q_3)$, $(q_1, q_3)$, and $(q_2, q_4)$. Step 4: Construct Minimal DFA Equivalence classes: $\{q_0, q_1, q_3\}$ (since $(q_0,q_1)$, $(q_1,q_3)$, $(q_0,q_3)$ are equivalent) $\{q_2, q_4\}$ (since $(q_2,q_4)$ are equivalent) $\{q_5\}$ (distinguishable from all others) Let $A = \{q_0, q_1, q_3\}$, $B = \{q_2, q_4\}$, $C = \{q_5\}$. Initial State: $A$ (contains $q_0$). Final States: $B$ (contains $q_2, q_4$). Minimized DFA Transitions: State $\delta(q, 0)$ $\delta(q, 1)$ $A = \{q_0, q_1, q_3\}$ $A$ (from $q_0 \to q_1$, $q_1 \to q_3$, $q_3 \to q_0$) $B$ (from $q_0 \to q_2$, $q_1 \to q_4$, $q_3 \to q_4$) $B = \{q_2, q_4\}$ $C$ (from $q_2 \to q_5$) / $B$ (from $q_4 \to q_4$) = $B$ or $C$? Let's recheck. $\delta(q_2, 0) = q_5 \in C$. $\delta(q_4, 0) = q_4 \in B$. This indicates $q_2$ and $q_4$ are distinguishable by input $0$. Let's re-examine the table marking for $(q_2, q_4)$. $\delta(q_2, 0) = q_5$, $\delta(q_4, 0) = q_4$. Is $(q_5, q_4)$ marked? Yes. So $(q_2, q_4)$ should be marked. This means $q_2$ and $q_4$ are *not* equivalent. Correction: My manual trace of Step 3 was flawed. Let's restart the marking. Corrected Step 3: Detailed Table-Filling Let's use a systematic table. Mark 'X' for distinguishable. Initial: Mark $(q_i, q_j)$ if one is final and other is non-final. Final states: $F = \{q_2, q_4\}$. Non-final: $N = \{q_0, q_1, q_3, q_5\}$. Mark: $(q_0,q_2), (q_0,q_4), (q_1,q_2), (q_1,q_4), (q_3,q_2), (q_3,q_4), (q_5,q_2), (q_5,q_4)$. q0 q1 q2 q3 q4 q5 q0 . X . X . q1 X . X . q2 X X X q3 X . q4 X q5 Pairs marked 'X' are distinguishable. '.' means unmarked. Iteration 1: $(q_0, q_1)$: $\delta(q_0,0)=q_1$, $\delta(q_1,0)=q_3 \implies (q_1,q_3)$ unmarked. $\delta(q_0,1)=q_2$, $\delta(q_1,1)=q_4 \implies (q_2,q_4)$ unmarked. $\implies (q_0,q_1)$ remains unmarked. $(q_0, q_3)$: $\delta(q_0,0)=q_1$, $\delta(q_3,0)=q_0 \implies (q_1,q_0)$ unmarked. $\delta(q_0,1)=q_2$, $\delta(q_3,1)=q_4 \implies (q_2,q_4)$ unmarked. $\implies (q_0,q_3)$ remains unmarked. $(q_0, q_5)$: $\delta(q_0,0)=q_1$, $\delta(q_5,0)=q_4 \implies (q_1,q_4)$ is marked. $\implies$ Mark $(q_0, q_5)$. $(q_1, q_3)$: $\delta(q_1,0)=q_3$, $\delta(q_3,0)=q_0 \implies (q_3,q_0)$ unmarked. $\delta(q_1,1)=q_4$, $\delta(q_3,1)=q_4 \implies (q_4,q_4)$ trivial. $\implies (q_1,q_3)$ remains unmarked. $(q_1, q_5)$: $\delta(q_1,0)=q_3$, $\delta(q_5,0)=q_4 \implies (q_3,q_4)$ is marked. $\implies$ Mark $(q_1, q_5)$. $(q_2, q_4)$: Both are final states. $\delta(q_2,0)=q_5$, $\delta(q_4,0)=q_4 \implies (q_5,q_4)$ is marked. $\implies$ Mark $(q_2, q_4)$. $(q_3, q_5)$: $\delta(q_3,0)=q_0$, $\delta(q_5,0)=q_4 \implies (q_0,q_4)$ is marked. $\implies$ Mark $(q_3, q_5)$. Updated table after Iteration 1: q0 q1 q2 q3 q4 q5 q0 . X . X X (q0,q5 marked) q1 X . X X (q1,q5 marked) q2 X X X (q2,q4 marked) q3 X X (q3,q5 marked) q4 X q5 Iteration 2: Check unmarked pairs again. $(q_0, q_1)$: $\delta(q_0,0)=q_1$, $\delta(q_1,0)=q_3 \implies (q_1,q_3)$ unmarked. $\delta(q_0,1)=q_2$, $\delta(q_1,1)=q_4 \implies (q_2,q_4)$ is now marked. $\implies$ Mark $(q_0, q_1)$. $(q_0, q_3)$: $\delta(q_0,0)=q_1$, $\delta(q_3,0)=q_0 \implies (q_1,q_0)$ is now marked. $\implies$ Mark $(q_0, q_3)$. $(q_1, q_3)$: $\delta(q_1,0)=q_3$, $\delta(q_3,0)=q_0 \implies (q_3,q_0)$ is now marked. $\implies$ Mark $(q_1, q_3)$. Final table (all pairs are now marked): q0 q1 q2 q3 q4 q5 q0 X X X X X q1 X X X X q2 X X X q3 X X q4 X q5 This implies all states are distinguishable from each other. This is an example where no minimization is possible, or I made a mistake in the example DFA or its transitions. Let's re-evaluate the initial DFA or pick a simpler one for clarity. Let's use a standard example for clarity. DFA: $Q=\{A,B,C,D,E,F\}$, $\Sigma=\{0,1\}$, Initial: $A$, Final: $F$. State $\delta(q,0)$ $\delta(q,1)$ A B C B A D C E F D E F E E F F F F Corrected Step 3: Table-Filling (with new example) Final states: $F=\{F\}$. Non-final states: $N=\{A,B,C,D,E\}$. Initial marking: all pairs $(q_i, F)$ are marked. A B C D E F A . . . . X B . . . X C . . X D . X E X F Iteration 1: $(A,B)$: $\delta(A,0)=B, \delta(B,0)=A \implies (B,A)$ unmarked. $\delta(A,1)=C, \delta(B,1)=D \implies (C,D)$ unmarked. $\implies (A,B)$ unmarked. $(A,C)$: $\delta(A,0)=B, \delta(C,0)=E \implies (B,E)$ unmarked. $\delta(A,1)=C, \delta(C,1)=F \implies (C,F)$ marked. $\implies$ Mark $(A,C)$. $(A,D)$: $\delta(A,0)=B, \delta(D,0)=E \implies (B,E)$ unmarked. $\delta(A,1)=C, \delta(D,1)=F \implies (C,F)$ marked. $\implies$ Mark $(A,D)$. $(A,E)$: $\delta(A,0)=B, \delta(E,0)=E \implies (B,E)$ unmarked. $\delta(A,1)=C, \delta(E,1)=F \implies (C,F)$ marked. $\implies$ Mark $(A,E)$. $(B,C)$: $\delta(B,0)=A, \delta(C,0)=E \implies (A,E)$ marked. $\implies$ Mark $(B,C)$. $(B,D)$: $\delta(B,0)=A, \delta(D,0)=E \implies (A,E)$ marked. $\implies$ Mark $(B,D)$. $(B,E)$: $\delta(B,0)=A, \delta(E,0)=E \implies (A,E)$ marked. $\implies$ Mark $(B,E)$. $(C,D)$: $\delta(C,0)=E, \delta(D,0)=E \implies (E,E)$ trivial. $\delta(C,1)=F, \delta(D,1)=F \implies (F,F)$ trivial. $\implies (C,D)$ remains unmarked. $(C,E)$: $\delta(C,0)=E, \delta(E,0)=E \implies (E,E)$ trivial. $\delta(C,1)=F, \delta(E,1)=F \implies (F,F)$ trivial. $\implies (C,E)$ remains unmarked. $(D,E)$: $\delta(D,0)=E, \delta(E,0)=E \implies (E,E)$ trivial. $\delta(D,1)=F, \delta(E,1)=F \implies (F,F)$ trivial. $\implies (D,E)$ remains unmarked. Updated table after Iteration 1: A B C D E F A . X X X X B X X X X C . . X D . X E X F Unmarked pairs: $(A,B), (C,D), (C,E), (D,E)$. Iteration 2: $(A,B)$: $\delta(A,0)=B, \delta(B,0)=A \implies (B,A)$ unmarked. $\delta(A,1)=C, \delta(B,1)=D \implies (C,D)$ unmarked. $\implies (A,B)$ remains unmarked. $(C,D)$: Unmarked in Iteration 1, still unmarked. $(C,E)$: Unmarked in Iteration 1, still unmarked. $(D,E)$: Unmarked in Iteration 1, still unmarked. No new marks. So, the unmarked pairs are equivalent. Step 4: Construct Minimal DFA (for new example) Equivalence classes: $\{A,B\}$ (from $(A,B)$ unmarked) $\{C,D,E\}$ (from $(C,D), (C,E), (D,E)$ unmarked) $\{F\}$ Let $Q_0 = \{A,B\}$, $Q_1 = \{C,D,E\}$, $Q_F = \{F\}$. Initial state: $Q_0$ (contains $A$). Final state: $Q_F$ (contains $F$). Minimized DFA Transitions: State $\delta(q,0)$ $\delta(q,1)$ $Q_0 = \{A,B\}$ $\delta(A,0)=B \in Q_0$ $\delta(B,0)=A \in Q_0$ $\implies Q_0$ $\delta(A,1)=C \in Q_1$ $\delta(B,1)=D \in Q_1$ $\implies Q_1$ $Q_1 = \{C,D,E\}$ $\delta(C,0)=E \in Q_1$ $\delta(D,0)=E \in Q_1$ $\delta(E,0)=E \in Q_1$ $\implies Q_1$ $\delta(C,1)=F \in Q_F$ $\delta(D,1)=F \in Q_F$ $\delta(E,1)=F \in Q_F$ $\implies Q_F$ $Q_F = \{F\}$ $\delta(F,0)=F \in Q_F$ $\implies Q_F$ $\delta(F,1)=F \in Q_F$ $\implies Q_F$ Diagram of Minimized DFA: Q0 Q1 QF 0 1 0 1 0,1