Discrete Mathematics:

Chapter 10 Machine Minimization

When writing a computer program or mathematical proof, the first goal is to create one that works. The second goal is to make it as simple as possible. The simpler a program or proof is, the easier it is to be certain that it really does work. The simpler it is, the easier it is to maintain and modify.

The finite state acceptor model for computing machines gives us a context in which this simplification can be fully realized. In this chapter we will see how, given a finite state acceptor, we can construct a new finite state acceptor of minimal complexity that recognizes exactly the same language. This work will lead to a very useful test to tell whether or not a given language is recognized by some FSA.

In general it is difficult to measure the complexity of a computer program or mathematical proof. A short program or proof can utilize complex logic while a long program or proof can be straightforward and even repetitive. In the case of a finite state acceptor \(M = \langle \Sigma, Q,s,\delta,Y\rangle\text{,}\) the number of internal states, \(|Q|\text{,}\) provides us with a useful measure of the complexity of \(M\text{.}\) Our goal is to find a method to generate from an FSA \(M\) recognizing a language \(L\text{,}\) a new FSA \(M'\) such that

1. \(M'\) also recognizes \(L\) and

2. no other FSA that recognizes \(L\) has fewer states than \(M'\text{.}\)

Such an FSA \(M'\) is called a minimal FSA. To see an example of a minimal FSA, let \(L_0\) be the language recognized by the FSA \(M_0\) in Figure 10.1.

You have just shown that any FSA \(N\) that recognizes \(L_0\) has at least as many states as \(M_0'\) that you constructed in Problem 10.3. Thus your FSA \(M'_0\) is a minimal FSA for \(M_0\) in Figure 10.1. Our goal is to find a general procedure that will produce, from any FSA \(M\text{,}\) a minimal FSA \(M'\) that recognizes the same language as \(M\text{.}\) Let \(\Sigma\) be any alphabet.

Note that no string in \(L\) begins with \(w\) if and only if \(R_w = \emptyset\text{.}\) Thus the set of all strings that are not a prefix of any member of \(L\) is an \(\equiv_L\)-class. We denote this \(\equiv_L\)-class by \(Z(L)\text{,}\) the set of strings whose right set is empty.

If \(w\in \{0,1\}^*\text{,}\) let \([w]\) denote the \(\equiv_0-class\) of~\(w\text{.}\) Problem 10.11 shows that there are exactly four different \(\equiv_{L_0}\)--classes:

The arrows in Figure 10.12 show where we go if we extend a string in any one of these classes by either 0 or~1.

Since \(\lambda\in L_0\text{,}\) we can take any string \(w\in \{0,1\}^*\) and find which \(\equiv_{L_0}\)-class \(w\) is in by tracing the diagram, building \(w\) by starting with \(\lambda\) in \(L_0\) and successively adding 0s or 1s on the right until we have \(w\text{.}\) Our ending point will be the \(\equiv_{L_0}\)–class of \(w\text{.}\) If we land in \(L_0\text{,}\) then \(w\in L_0\text{;}\) otherwise \(w \notin L_0\text{.}\) What we have done is to find a systematic way to build an FSA \(M_0''\)for the language \(L_0\) using the \(\equiv_{L_0}\)-classes as internal states and taking \(L_0\) as the only accepting state (see Figure 10.12). In fact, according to Problem 10.4, this is a minimal FSA to recognize \(L_0\text{!}\)

We would like to mimic this construction, starting with an arbitrary language \(L \subseteq \Sigma^*\) to see if we can construct a FSA for \(L\) with a minimum number of states. In order to do this, it will be helpful to start with a broader setting in which we make no restrictions on the number of states in \(Q\text{.}\)

While it is not possible to build a GSA with infinitely many states, it will be helpful here to look first for a GSA for \(L\) and then see when we can find one with only finitely many states. Following the construction of \(M_0''\text{,}\) we define

where

Part 2 of Problem 10.14 implies that \(\delta_L\) is well defined.

Recall that \(\Delta_L\) is the extension of \(\delta_L\) to all of \(Q_L \times \Sigma^*\text{.}\)

This shows that every language \(L \subseteq \Sigma^*\) is recognized by some GSA. The GSA \(G_L\) is called the standard \(GSA\) for \(L\text{.}\)

Example 10.17 shows how GSAs with infinitely many states can naturally arise from simply defined languages. But our real interest is in FSAs, which might actually be built. Do you think that there could be an FSA that recognizes \(L_{10}\text{?}\) We can now exhibit a special feature of standard GSAs which at last proves for certain that there is not.

Given a language \(L\subseteq \Sigma^*\text{,}\) we can now determine whether or not it is recognized by some FSA and, if it is, construct a minimal FSA that recognizes it. All we need to do is to calculate right sets to determine the \(\equiv_L\)-classes of \(Q_L\text{.}\) We state what we have found as a final theorem.

To see this, let \(w\in \{0,1\}^*\text{.}\)

1. If \(w\in ({\bf 00 \cup 11})^*\text{,}\) then its right set is \(({\bf 00 \cup 11})^*\text{.}\)

2. If \(w\in ({\bf 00 \cup 11})^*{\bf 0}\text{,}\) then its right set is \({\bf 0}({\bf 00 \cup 11})^*\text{.}\)

3. If \(w\in ({\bf 00 \cup 11})^*{\bf 1}\text{,}\) then its right set is \({\bf 1}({\bf 00 \cup 11})^*\text{.}\)

4. Otherwise its right set is \(\pmb\varnothing\text{.}\)

Consequently there are only four different \(\equiv_{L_0}\)-classes in \(Q_{L_0}\text{.}\)

To see this, consider the infinite set \(\{a, a^2, a^3, a^4, \dots\}\) of strings in \(\{a,b\}^*\text{.}\) For each positive integer \(n\text{,}\) the string \(b^n\) is in the right set of \(a^n\) but not in the right set of \(a^m\) for any \(m\neq n\text{.}\) Consequently \(Q_{L_{10}}\) has infinitely many different \(\equiv_{L_{10}}\)-classes.

For the next five languages \(L\text{,}\) show that \(Q_L\) is finite and construct its standard FSA.

For the next four languages \(L\text{,}\) show that \(Q_L\) is infinite and therefore \(L\) is not recognized by any FSA.