1.Minimizing the Number of States in a DFA§

Why do we need to do this?

If you have an NFA with $n$ states, what is the maximum number of states in the equivalent DFA created?

Minimization Algorithm Concept

Identify states that are indistinguishable

Definition: Two states $p$ and $q$ are indistinquishable if for all $w \in \Sigma^*$

$\delta^*(q, w) \in F \Rightarrow \delta^*(p, w) \in F$

$\delta^*(p, w) \not\in F \Rightarrow \delta^*(q, w) \not\in F$

Definition: Two states $p$ and $q$ are distinquishable if $\exists w \in \Sigma^*$ such that

$\delta^*(q, w) \in F \Rightarrow \delta^*(p, w) \not \in F$ OR

$\delta^*(q, w) \not \in F \Rightarrow \delta^*(p, w) \in F$

$p$ and $q$ appear to be different.

<< What does this mean? >>

All that an acceptor cares about is accepting or rejecting strings.

Select any pair of states, $p$ and $q$ .

If, in either case, we accept/reject the exact same set set of strings, then there is no difference between them.
So, we can combine them.
Remember the definition for $\delta^*(p, w)$ . Look at things this way: It is telling us that we don’t care about the prior history before we got to the current state with whatever remains of the input.

Distinguishability is an equivalence relation.

<<Look at first slide in frameset of Module 3.6.2.>>

Look at A on a, ab. Look at F on a, ab. Look at D on a, ab.

Remove all inaccessible states.
Consider all pairs of states $(p, q)$ . If $p \in F$ and $q \not \in F$ or vice versa, then mark the pair $(p, q)$ as distinguishable.
Repeat the following step until no previously unmarked pairs are marked:

For all pairs $(p, q)$ and all $a \in \Sigma$ , compute $\delta(p, a) = p_a$ and $\delta(q, a) = q_a$ .

If the pair $(p_a, q_a)$ is marked as distinguishable, mark $(p, q)$ as distinguishable.

Gather together the indistingushable pairs into groups. Each group is a state in the new machine.

Finally, a (new machine) state $q_i$ is final if and only if any of its base states (from the old machine) are final.

<<See Frameset 3.6.2>>