1.2. Minimizing the Number of States in a DFA¶
1.2.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?
1.2.2. Minimization Algorithm Concept¶
Identify states that are indistinguishable
These states will collectively form a new state in the minimized machine.
1.2.3. Distinguishable States (1)¶
Definition: Two states p and q are indistinquishable if for all w∈Σ∗
δ∗(q,w)∈F⇒δ∗(p,w)∈Fδ∗(p,w)∉F⇒δ∗(q,w)∉FDefinition: Two states p and q are distinquishable if ∃w∈Σ∗ such that
δ∗(q,w)∈F⇒δ∗(p,w)∉F ORδ∗(q,w)∉F⇒δ∗(p,w)∈Fp and q appear to be different.
<< What does this mean? >>
1.2.4. Distinguishable States (2)¶
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 δ∗(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.
1.2.5. Example 1 (1)¶
<<Look at first slide in frameset of Module 3.5.2.>>
Look at A on a, ab. Look at F on a, ab. Look at D on a, ab.
1.2.6. Algorithm¶
Remove all inaccessible states.
Consider all pairs of states (p,q). If p∈F and q∉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∈Σ, compute δ(p,a)=pa and δ(q,a)=qa.If the pair (pa,qa) 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 qi is final if and only if any of its base states (from the old machine) are final.
1.2.7. Example 1¶
<<See Frameset 3.5.2>>