Minimizing the States of an NFA

You might imagine that the same state-partition technique that minimizes the states of a DFA could also be used to find a minimum-state NFA equivalent to a given NFA or DFA. While we can, by a process of exhaustive enumeration, find an NFA with as few states as possible accepting a given regular language, we cannot simply group the states of some given NF.A. for the language.

An example is in Fig. 4.13. None of the three states an; equivalent. Surely accepting state В is distinguishable from nonaccepting states A and C. However, A and С arc distinguishable by input 0. The succes.sors of С are A alone, which does not include an accepting state, while the successors of A are {A.B}, which does include an accepting state. Thus, grouping equivalent states does not reduce the number of states of Fig. 4.13.

However, we can find a smaller NF.A for the same language if we simply remove state C. Note that A and В alone accept all strings ending in 0, while adding state С does not allow us to ж:серг, any other strings.

symbol are also indistinguishable. The reiison is that if we could disthiguish the successors, then wo could distinguish p from q.

Neither Л/ nor Л could have an inaccessible state, or else we could eliminate that state and have an even smaller DFA for the same language!. Thus, every state of M is indistinguishable from at least one state of iV. To see why, suppose p is a state of M. Then there is some string 0102 ak that takes the start state of Л/ to state p. This string also takes the start, state of -V to some state q. Since we know the start states are indistinguishable, we also know that their successors under input symbol a\ are indistinguishabk;. Then, the successors of those states on input 02 are indistinguishable, and .so on, until we conclude

Figure 4.13: .An NFA that cannot be minimized by state equivalence

that p and q are indistinguishable,

Since has fewer states than M, there are two states of m that are in-distingnishabie from the same state of Л, and therefore indistinginshable from each otiier. Bnt Л/ was designed so that all its states are distinguishable from cm-h other. We have a contradiction, so the assumption that Л* exists is wrong, and Af in fact has as few states as any equivalent DFA for A. Formally, wc have proved:

Theorem 4.26: If A is a DFA, and M the DFA constructed firom .4 by the algorithm described in the statement of Theorem 4,24, then M has as few states as any DFA oqui-vralent to .4. □

In fact we can say something even stronger than Theorem 4.26. There nmst be a one-to-one correspondence between the states of any other minimum-state Л and the DF.A M. The reason is that we argued above how each state of M must be equivalent to ont; state of N, and no state of M can be equivalent to two states of N, We can similarly argue that no state of N can be equivalent to two states of AI, although each state of N must be equivalent to one of APs states. Thus, the minunum-state DF. equivalent to .4 is unique except for a possible renaming of the states.

Figure 4.14: A DFA to be minimized

4,4.5 Exercises for Section 4.4 * Exercise 4.4.1: In Fig. 4.14 is the transition table of a DFA.

a) Draw the table of distinguishabilities for this automaton.

b) Construct the mininmm-state equivalent DFA. Exercise 4.4.2: Repeat Exercise 4.4.1 for the DF.A of Fig 4.15.

!! Exercise 4.4,3: Suppose that p are q are distinguishable states of a given DF.4 A with n states. As a function of тг, what is the tightest upper bound on how long the shortest string that distinguishes p from q can be?

Figure 4.15: Another DFA to ininimize

4.5 Summary of Chapter 4

f The Pumping Lemma: If a language is regular, then every sufficiently long string in the langnaage has a nonempty substring that can be pumped, that is, repeated any number of times while the resulting strings are also in the langnage. This fact can be used to prove that many different languages are not regular.

¥ Operations That Preserve the Property of Being a Regular Language: There are many operations that, when applied to regular languages, yield a regidar- language as a residt. Among these are union, concatenation, closure, intersection, complementation, difference, reversal, homomorphism (replacement of each symbol by an associated string), and inverse homomorphism.

f Testing Emptiness of Regular Languages: There is an algorithm that, given a representation of a regular language, such as an automaton or regular expression, tells whether or not the represented language is the empty set.

4- Testing Membership in a Regular Language: There is an algorithm that, given a string and a representation of a regular language, tells whether or not the string is in the language.

f Testing Distinguishahility of States: Two states of a DF.A aie distinguishable if there is an input string that takes exactly one of the two states to an accepting state. By starting with only tlie fact that pairs consisting of (me accepting and one nonaccepting state are distinguishable, and trying to discover addition pairs of distinguishable states by finding pairs whose successors on one in])ut symbol are distinguishable, we can discover all pairs of distinguishable states.