DFA Minimisation General Algorithm

COMP218 Lectures 2021-10-21

Finding Indistinguishable States

If $q$ is accepting and $q’$ is rejecting, mark $(q,q’)$ as distinguishable:
```
 stateDiagram-v2
 direction LR
 [*] --> q(x)
 q'(x) --> [*]
```

If $(q_1,q_1;)$ are marked, mark $(q_2,q_2’)$ as distinguishable:

 stateDiagram-v2
 direction LR
 q2(x) --> q1(x):a
 q2'(x) --> q1'(x):a

Unmarked pairs are indistinguishable, merge them into groups.

Example of DFA Minimisation

Consider the following DFA to be minimised:

stateDiagram-v2
direction LR
[*] --> qe
qe --> q0:0
qe --> q1:1
q0 --> q00:0
q00 --> q01:1
q0 --> q01:1
q1 --> q10:0
q1 --> q11:1
q11 --> [*]
q00 --> q00:0
q01 --> q10:0
q01 --> q11:1
q10 --> q00:0
q10 --> q01:1
q11 --> q10:0
q11 --> q11:1

This would produce the following table:

	$q_\epsilon$	$q_0$	$q_1$	$q_{00}$	$q_{01}$	$q_{10}$
$q_0$
$q_1$	×	×
$q_{00}$			×
$q_{01}$	×	×		×
$q_{10}$			×		×
$q_{11}$	×	×	×	×	×	×	×

The top-right diagonal is unused.

To begin mark all accept states ($q_{11}$) as distinguishable.
Go through each state pair and mark it as distinguishable if is transitions to a distinguishable state pair.

For each state in the pair, transition via 0. The two states which each state transitions to are result of the state pair transition via 0. Repeat this for 1 to find the other state pair.
Repeat (2.) for all states until there is no change.
Apply rule 3 and remove indistinguishable states from the state graph.

Grouping Unmarked states

We can group unmarked states by drawing lines between each unmarked pair:

flowchart
subgraph A
qe --- q0 & q00 & q10
q0 --- q00 & q10
end
subgraph B
q1 --- q01
end
q00 --- q10
subgraph C
q11
end

Each group becomes a state. Analyse the transitions between states in order to determine the transitions between groups:

stateDiagram-v2
direction LR
[*] --> qe
state A{
qe
q0
q00
q10
}
state B{
q1
q01
}
state C{
q11
}
qe --> q0:0
qe --> q1:1
q0 --> q00:0
q00 --> q01:1
q0 --> q01:1
q1 --> q10:0
q1 --> q11:1
q11 --> [*]
q00 --> q00:0
q01 --> q10:0
q01 --> q11:1
q10 --> q00:0
q10 --> q01:1
q11 --> q10:0
q11 --> q11:1

Remember to include self loops.

This gives the following minimal state diagram:

stateDiagram-v2
direction LR
[*] --> A
A --> A:0
A --> B:1
B --> A:0
B --> C:1
C --> A:0
C --> C:1
C --> [*]

We know it is minimal as all the states are distinguishable.