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>>