SI342: State Minimization Algorithm

Our proof is just to augment the Minmization algorithm so that it constructs the strings we need for us. The following produces, for every pair of group indices $i \lt j$, a string $w_{i,j}$ such that either processing $w_{i,j}$ in $M$ starting from any state in $G_i$ is accepting and any state in $G_j$ is non-accepting, or vice versa. Since the states in $M'$ are precisely the groups from the algorithm, these $w_{i,j}$'s define the $u$'s we need.

Algorithm: Augmented DFA Minimization
Input: DFA M = (Q,Σ,δ,s,W), where W ≠ Q, W ≠ ∅, and there are no unreachable states.
Output: DFA M' such that L(M) = L(M') and no DFA with fewer states than M' accepts L(M) and a table w, such that for every two states Gi and Gj in M' with i < j, wi,j is a string that takes M' from state Gi to an accepting state and from Gj to a non-accepting state, or vice versa.

set $G_1 = Q - W$ and $G_2 = W$
set $w$ to a $2\times 2$ table where $w_{1,2} = \lambda$. [Note: $(G_1,w_{1,2}) \Rightarrow^* (G_1,w_{1,2})$ (non-accept), and $(G_2,w_{1,2}) \Rightarrow^* (G_2,w_{1,2})$ (accept)]
At this point we have groups $G_1,\ldots,G_n$, and for any indices i < j, processing $w_{i,j}$ starting at $G_i$ ends up in a state with opposite accept/reject status than processing $w_{i,j}$ starting at $G_j$.
find a group $G_m$ in which not all states have the same signature, divide it into subgroups in which sig(q) is the same for every state q in the subgroup.
Suppose $G_m$ is getting split into $k$ new groups. We'll remove $G_m$ and call the new groups $G'_{n+1},\ldots,G'_{n+k}$. We'll define the new $w_{i,j}$'s first. Afterwards, we can renumber groups to give them consecutive numbers.
Note: if $G'_i$ and $G'_j$ are distinct subgroups from splitting $G_m$, it means that there is a character $x$, distinct groups $G_a$ and $G_b$, and states $p\in G'_i$ and $q\in G'_j$ such that $\delta(p,x) \in G_a$ and $\delta(q,x) \in G_b$. $$ \text{new }w_{i,j} = \left\{ \begin{array}{cl} w_{i,j} & \text{ if } i,j\in\left(\{1,\ldots,n\} - \{m\}\right)\\ w_{i,m} & \text{ if } i\in\left(\{1,\ldots,n\} - \{m\}\right)\text{ and } j=m\\ x w_{a,b} & \text{ if } i,j\in\{n+1,\ldots,n+k\} \text{, where $x$, $a$ and $b$ are as described in the note above} \end{array} \right. $$ Important! Reindex the groups and the table $w$ so the groups are all $G$ groups (no $G'$ groups) and the indices are consecutive integers starting from 1.
if any group was subdivided, set $n$ to the number of groups and go back to (2) and repeat
set M' = ({G1,...,Gn},Σ,δ',s',W') where
- s' = Gk, where s ∈ Gk, and
- W' = {Gi | Gi ⊆ W }, and
- δ'(Gi,x) = Gj, where for any q ∈ Gi we have δ(q,x) ∈ Gj.

Machine $M'$	Table $w$	Commentary
	\| 1 2 3 4 -+----------------- 1\| λ b ab \| 2\| λ λ \| 3\| b \| 4\|	Just to see what this means, consider one table entry: $w_{1,4} = ab$. This means that starting from state $G_1$ and reading $ab$ should result in the opposite accept/reject status as starting in $G_4$ and reading $ab$. Let's see: $$ (G_1,ab) \Rightarrow_{M'} (G_1,b) \Rightarrow_{M'} (G_1,\lambda), G_1 \notin W' $$ whereas ... $$ (G_4,ab) \Rightarrow_{M'} (G_3,b) \Rightarrow_{M'} (G_2,\lambda), G_2 \in W' $$ ... as advertised!

Machine $M'$

Table $w$

Commentary

 | 1   2   3   4
-+-----------------
1|     λ   b   ab
 |    
2|         λ   λ
 |
3|             b
 |
4|

Just to see what this means, consider one table entry: $w_{1,4} = ab$. This means that starting from state $G_1$ and reading $ab$ should result in the opposite accept/reject status as starting in $G_4$ and reading $ab$. Let's see: $$ (G_1,ab) \Rightarrow_{M'} (G_1,b) \Rightarrow_{M'} (G_1,\lambda), G_1 \notin W' $$ whereas ... $$ (G_4,ab) \Rightarrow_{M'} (G_3,b) \Rightarrow_{M'} (G_2,\lambda), G_2 \in W' $$ ... as advertised!

$M_{\text{new}}$	Running CounterExampleFinder
	Step 1: $u_1 = aa, u_2 = bb, u_3 = a, u_4 = \lambda$ Step 2: $u_1:\ (q_0,aa) \rightarrow_{M_{new}}^* (q_0,\lambda)$ $u_2:\ (q_0,bb) \rightarrow_{M_{new}}^* (q_2,\lambda)$ $u_3:\ (q_0,a) \rightarrow_{M_{new}}^* (q_1,\lambda)$ $u_4:\ (q_0,\lambda) \rightarrow_{M_{new}}^* (q_0,\lambda)$ So $i=1,j=4$ since $M_{\text{new}}$ goes to state $q_0$ on both $u_1$ and $u_4$ Step 3: $u_1 = u_i w_{i,j} = u_1 w_{1,4} = aaab$ Step 4: $u_2 = u_j w_{i,j} = u_4 w_{1,4} = ab$ Step 5: $u = u_1 = aaab$, since $u_1 \notin L(M')$ but $u_1 \in L(M_{new})$ So the string aaab proves that Mnew does not accept the same language as M'.

$M_{\text{new}}$

Running CounterExampleFinder

Step 1: $u_1 = aa, u_2 = bb, u_3 = a, u_4 = \lambda$
Step 2:
  $u_1:\ (q_0,aa) \rightarrow_{M_{new}}^* (q_0,\lambda)$
  $u_2:\ (q_0,bb) \rightarrow_{M_{new}}^* (q_2,\lambda)$
  $u_3:\ (q_0,a) \rightarrow_{M_{new}}^* (q_1,\lambda)$
  $u_4:\ (q_0,\lambda) \rightarrow_{M_{new}}^* (q_0,\lambda)$
  So $i=1,j=4$ since $M_{\text{new}}$ goes to state $q_0$ on both $u_1$ and $u_4$
Step 3: $u_1 = u_i w_{i,j} = u_1 w_{1,4} = aaab$
Step 4: $u_2 = u_j w_{i,j} = u_4 w_{1,4} = ab$
Step 5: $u = u_1 = aaab$, since $u_1 \notin L(M')$ but $u_1 \in L(M_{new})$

So the string aaab proves that Mnew does not accept the same language as M'.