Finite-State Automata and Regular Languages

Section 17.4 Finite-State Automata and Regular Languages

We know now that our two models for mechanical language recognition actually recognize the same class of languages. The question still remains: do they recognize the same class of languages as the class generated mechanically by regular expressions? The answer turns out to be ``yes". There are two parts to proving this: first that every language generated can be recognized, and second that every language recognized can be generated.

Subsection 17.4.1 All Regular Languages are Recognized by NFAs

Theorem 17.4.1.

Every language generated by a regular expression can be recognized by an NFA.

Proof.

The proof of this theorem is a nice example of a proof by induction on the structure of regular expressions. The definition of regular expression is inductive: \(\Phi\) , \(\varep\text{,}\) and \(a\) are the simplest regular expressions, and then more complicated regular expressions can be built from these. We will show that there are NFAs that accept the languages generated by the simplest regular expressions, and then show how those machines can be put together to form machines that accept languages generated by more complicated regular expressions. Consider the regular expression \(\Phi\text{.}\) \(L(\Phi) = \{\}\text{.}\) Here is a machine that accepts \(\{\}\text{:}\)

Diagram of an NFA that accepts \(L(\Phi) = \{\}\text{.}\) — Figure 17.4.2.

Consider the regular expression \(\varep\text{.}\) \(L(\varep) = \{\varepsilon\}\text{.}\) Here is a machine that accepts \(\{\varepsilon\}\text{:}\)

Diagram of an NFA that accepts \(L(\varep) = \{\varepsilon\}\text{.}\) — Figure 17.4.3.

Consider the regular expression \(a\text{.}\) \(L(a) = \{a\}\text{.}\) Here is a machine that accepts \(\{a\}\text{:}\)

Diagram of an NFA that accepts \(L(a) = \{a\}\text{.}\) — Figure 17.4.4.

Now suppose that you have NFAs that accept the languages generated by the regular expressions \(r_1\) and \(r_2\text{.}\) Building a machine that accepts \(L(r_1 \REOR r_2)\) is fairly straightforward: take an NFA \(M_1\) that accepts \(L(r_1)\) and an NFA \(M_2\) that accepts \(L(r_2)\text{.}\) Introduce a new state \(q_{new}\text{,}\) connect it to the start states of \(M_1\) and \(M_2\) via \(\varepsilon\)-transitions, and designate it as the start state of the new machine. No other transitions are added. The final states of \(M_1\) together with the final states of \(M_2\) are designated as the final states of the new machine. It should be fairly clear that this new machine accepts exactly those strings accepted by \(M_1\) together with those strings accepted by \(M_2\text{:}\) any string \(w\) that was accepted by \(M_1\) will be accepted by the new NFA by starting with an \(\varep\)-transition to the old start state of \(M_1\) and then following the accepting path through \(M_1\text{;}\) similarly, any string accepted by \(M_2\) will be accepted by the new machine; these are the only strings that will be accepted by the new machine, as on any input \(w\) all the new machine can do is make an \(\varep\)-move to \(M_1\)’s (or \(M_2\)’s) start state, and from there \(w\) will only be accepted by the new machine if it is accepted by \(M_1\) (or \(M_2\)). Thus, the new machine accepts \(L(M_1) \cup L(M_2)\text{,}\) which is \(L(r_1) \cup L(r_2)\text{,}\) which is exactly the definition of \(L(r_1 \REOR r_2)\text{.}\)

Diagram of an NFA that accepts \(L(r_1 \REOR r_2)\text{.}\) — Figure 17.4.5.

Remark 17.4.6. A pause before we continue:.

Note that for the simplest regular expressions, the machines that we created to accept the languages generated by the regular expressions were in fact DFAs. In our last case above, however, we needed \(\varep\)-transitions to build the new machine, and so if we were trying to prove that every regular language could be accepted by a DFA, our proof would be in trouble. THIS DOES NOT MEAN that the statement ``every regular language can be accepted by a DFA" is false, just that we can’t prove it using this kind of argument, and would have to find an alternative proof.

Suppose you have machines \(M_1\) and \(M_2\) that accept \(L(r_1)\) and \(L(r_2)\) respectively. To build a machine that accepts \(L(r_1)L(r_2)\) proceed as follows. Make the start state \(q_{01}\) of \(M_1\) be the start state of the new machine. Make the final states of \(M_2\) be the final states of the new machine. Add \(\varep\)-transitions from the final states of \(M_1\) to the start state \(q_{02}\) of \(M_2\text{.}\)

Diagram of an NFA that accepts \(L(r_1)L(r_2)\text{.}\) — Figure 17.4.7.

It should be fairly clear that this new machine accepts exactly those strings of the form \(xy\) where \(x\in L(r_1)\) and \(y \in L(r_2)\text{:}\) first of all, any string of this form will be accepted because \(x\in L(r_1)\) implies there is a path that consumes \(x\) from \(q_{01}\) to a final state of \(M_1\text{;}\) a \(\varep\)-transition moves to \(q_{02}\text{;}\) then \(y \in L(r_2)\) implies there is a path that consumes \(y\) from \(q_{02}\) to a final state of \(M_2\text{;}\) and the final states of \(M_2\) are the final states of the new machine, so \(xy\) will be accepted. Conversely, suppose \(z\) is accepted by the new machine. Since the only final states of the new machine are in the old \(M_2\text{,}\) and the only way to get into \(M_2\) is to take a \(\varep\)-transition from a final state of \(M_1\text{,}\) this means that \(z=xy\) where \(x\) takes the machine from its start state to a final state of \(M_1\text{,}\) a \(\varep\)-transition occurs, and then \(y\) takes the machine from \(q_{02}\) to a final state of \(M_2\text{.}\) Clearly, \(x\in L(r_1)\) and \(y \in L(r_2)\text{.}\)

We leave the construction of an NFA that accepts \(L(r^*)\) from an NFA that accepts \(L(r)\) as an exercise.

Subsection 17.4.2 Every Language Recognized by an NFA is Regular

Theorem 17.4.8.

Every language that is accepted by a DFA or an NFA is generated by a regular expression.

Proving this result is actually fairly involved and not very illuminating. Below we will give an illustrative example of how one might actually go about extracting a regular expression from an NFA or a DFA. You can go on to read the proof if you are interested.

Proof.

We prove that the language accepted by a DFA is regular. The proof for NFAs follows from the equivalence between DFAs and NFAs.

Suppose that \(M\) is a DFA, where \(M=(Q,\Sigma,q_0,\delta,F)\text{.}\) Let \(n\) be the number of states in \(M\text{,}\) and write \(Q=\{q_0,q_1,\dots,q_{n-1}\}\text{.}\) We want to consider computations in which \(M\) starts in some state \(q_i\text{,}\) reads a string \(w\text{,}\) and ends in state \(q_k\text{.}\) In such a computation, \(M\) might go through a series of intermediates states between \(q_i\) and \(q_k\text{:}\)

\begin{equation*} q_i\longrightarrow p_1\longrightarrow p_2 \cdots\longrightarrow p_r\longrightarrow q_k \end{equation*}

We are interested in computations in which all of the intermediate states--- \(p_1,p_2,\dots,p_r\)---are in the set \(\{q_0,q_1,\dots,q_{j-1}\}\text{,}\) for some number \(j\text{.}\) We define \(R_{i,j,k}\) to be the set of all strings \(w\) in \(\Sigma^*\) that are consumed by such a computation. That is, \(w\in R_{i,j,k}\) if and only if when \(M\) starts in state \(q_i\) and reads \(w\text{,}\) it ends in state \(q_k\text{,}\) and all the intermediate states between \(q_i\) and \(q_k\) are in the set \(\{q_0,q_1,\dots,q_{j-1}\}\text{.}\) \(R_{i,j,k}\) is a language over \(\Sigma\text{.}\) We show that \(R_{i,j,k}\) for \(0\leq i \lt n , 0\leq j \leq n, 0\leq k lt n\text{.}\)

Consider the language \(R_{i,0,k}\text{.}\) For \(w\in R_{i,0,k}\text{,}\) the set of allowable intermediate states is empty. Since there can be no intermediate states, it follows that there can be at most one step in the computation that starts in state \(q_i\text{,}\) reads \(w\text{,}\) and ends in state \(q_k\text{.}\) So, \(|w|\) can be at most one. This means that \(R_{i,0,k}\) is finite, and hence is regular. (In fact, \(R_{i,0,k}=\{a\in\Sigma\st \delta(q_i,a)=q_k\}\text{,}\) for \(i\ne k\text{,}\) and \(R_{i,0,i}=\{\varep\}\cup\{a\in\Sigma\st \delta(q_i,a)=q_i\}\text{.}\) Note that in many cases, \(R_{i,0,k}\) will be the empty set.)

We now proceed by induction on \(j\) to show that \(R_{i,j,k}\) is regular for all \(i\) and \(k\text{.}\) We have proved the base case, \(j=0\text{.}\) Suppose that \(0\leq j \lt n \) we already know that \(R_{i,j,k}\) is regular for all \(i\) and all \(k\text{.}\) We need to show that \(R_{i,j+1,k}\) is regular for all \(i\) and \(k\text{.}\) In fact,

\begin{equation*} R_{i,j+1,k}=R_{i,j,k}\cup \left( R_{i,j,j}R_{j,j,j}^*R_{j,j,k}\right) \end{equation*}

which is regular because \(R_{i,j,k}\) is regular for all \(i\) and \(k\text{,}\) and because the union, concatenation, and Kleene star of regular languages are regular.

To see that the above equation holds, consider a string \(w\in\Sigma^*\text{.}\) Now, \(w\in R_{i,j+1,k}\) if and only if when \(M\) starts in state \(q_i\) and reads \(w\text{,}\) it ends in state \(q_k\text{,}\) with all intermediate states in the computation in the set \(\{q_0,q_1,\dots,q_j\}\text{.}\) Consider such a computation. There are two cases: Either \(q_j\) occurs as an intermediate state in the computation, or it does not. If it does not occur, then all the intermediate states are in the set \(\{q_0,q_1,\dots,q_{j-1}\}\text{,}\) which means that in fact \(w\in R_{i,j,k}\text{.}\) If \(q_j\) does occur as an intermediate state in the computation, then we can break the computation into phases, by dividing it at each point where \(q_j\) occurs as an intermediate state. This breaks \(w\) into a concatenation \(w=xy_1y_2\cdots y_rz\text{.}\) The string \(x\) is consumed in the first phase of the computation, during which \(M\) goes from state \(q_i\) to the first occurrence of \(q_j\text{;}\) since the intermediate states in this computation are in the set \(\{q_0,q_1,\dots,q_{j-1}\}, x\in R_{i,j,j}\text{.}\) The string \(z\) is consumed by the last phase of the computation, in which \(M\) goes from the final occurrence of \(q_j\) to \(q_k\text{,}\) so that \(z\in R_{j,j,k}\text{.}\) And each string \(y_t\) is consumed in a phase of the computation in which \(M\) goes from one occurrence of \(q_j\) to the next occurrence of \(q_j\text{,}\) so that \(y_r\in R_{j,j,j}\text{.}\) This means that \(w=xy_1y_2\cdots y_rz\in R_{i,j,j}R_{j,j,j}^*R_{j,j,k}\text{.}\)

We now know, in particular, that \(R_{0,n,k}\) is a regular language for all \(k\text{.}\) But \(R_{0,n,k}\) consists of all strings \(w\in\Sigma^*\) such that when \(M\) starts in state \(q_0\) and reads \(w\text{,}\) it ends in state \(q_k\) (with \textbf{no} restriction on the intermediate states in the computation, since every state of \(M\) is in the set \{q_0,q_1,\dots,q_{n-1}\}). To finish the proof that \(L(M)\) is regular, it is only necessary to note that

\begin{equation*} L(M)=\bigcup_{q_k\in F} R_{0,n,k} \end{equation*}

which is regular since it is a union of regular languages. This equation is true since a string \(w\) is in \(L(M)\) if and only if when \(M\) starts in state \(q_0\) and reads \(w\text{,}\) in ends in some accepting state \(q_k\in F\text{.}\) This is the same as saying \(w\in R_{0,n,k}\) for some \(k\) with \(q_k\in F\text{.}\)

Example 17.4.9.

Consider the DFA shown below:

Diagram of a DFA to extract regular expression from. — Figure 17.4.10.

Note that there is a loop from state \(q_2\) back to state \(q_2\text{:}\) any number of \(a\)’s will keep the machine in state \(q_2\text{,}\) and so we label the transition with the regular expression \(a^*\text{.}\) We do the same thing to the transition labeled \(b\) from \(q_0\text{.}\) (Note that the result is no longer a DFA, but that doesn’t concern us, we’re just interested in developing a regular expression.)

Altered diagram from above. — Figure 17.4.11.

Next we note that there is in fact a loop from \(q_1\) to \(q_1\) via \(q_0\text{.}\) A regular expression that matches the strings that would move around the loop is \(ab^*a\text{.}\) So we add a transition labeled \(ab^*a\) from \(q_1\) to \(q_1\text{,}\) and remove the now-irrelevant \(a\)-transition from \(q_1\) to \(q_0\text{.}\) (It is irrelevant because it is not part of any other loop from \(q_1\) to \(q_1\text{.}\))

Next we note that there is also a loop from \(q_1\) to \(q_1\) via \(q_2\text{.}\) A regular expression that matches the strings that would move around the loop is \(ba^*b\text{.}\) Since the transitions in the loop are the only transitions to or from \(q_2\text{,}\) we simply remove \(q_2\) and replace it with a transition from \(q_1\) to \(q_1\text{.}\)

It is now clear from the diagram that strings of the form \(b^*a\) get you to state \(q_1\text{,}\) and any number of repetitions of strings that match \(ab^*a\) or \(ba^*b\) will keep you there. So the machine accepts \(L(b^*a(ab^*a\REOR ba^*b)^*)\text{.}\)

We have already seen that if two languages \(L_1\) and \(L_2\) are regular, then so are \(L_1 \cup L_2\text{,}\) \(L_1L_2\text{,}\) and \(L_1^*\) (and of course \(L_2^*\)). We have not yet seen, however, how the common set operations intersection and complementation affect regularity. Is the complement of a regular language regular? How about the intersection of two regular languages?

Both of these questions can be answered by thinking of regular languages in terms of their acceptance by DFAs. Let’s consider first the question of complementation. Suppose we have an arbitrary regular language \(L\text{.}\) We know there is a DFA \(M\) that accepts \(L\text{.}\) Pause a moment and try to think of a modification that you could make to \(M\) that would produce a new machine \(M'\) that accepts \(\overline{L}\text{....}\) Okay, the obvious thing to try is to make \(M'\) be a copy of \(M\) with all final states of \(M\) becoming non-final states of \(M'\) and vice versa. This is in fact exactly right: \(M'\) does in fact accept \(\overline{L}\text{.}\) To verify this, consider an arbitrary string \(w\text{.}\) The transition functions for the two machines \(M\) and \(M'\) are identical, so \(\delta^* (q_0, w)\) is the same state in both \(M\) and \(M'\text{;}\) if that state is accepting in \(M\) then it is non-accepting in \(M'\text{,}\) so if \(w\) is accepted by \(M\) it is not accepted by \(M'\text{;}\) if the state is non-accepting in \(M\) then it is accepting in \(M'\text{,}\) so if \(w\) is not accepted by \(M\) then it is accepted by \(M'\text{.}\) Thus \(M'\) accepts exactly those strings that \(M\) does not, and hence accepts \(\overline{L}\text{.}\)

It is worth pausing for a moment and looking at the above argument a bit longer. Would the argument have worked if we had looked at an arbitrary language \(L\) and an arbitrary NFA \(M\) that accepted \(L\text{?}\) That is, if we had built a new machine \(M'\) in which the final and non-final states had been switched, would the new NFA \(M'\) accept the complement of the language accepted by \(M\text{?}\) The answer is ``not necessarily". Remember that acceptance in an NFA is determined based on whether or not at least one of the states reached by a string is accepting. So any string \(w\) with the property that \(\partial^*(q_0, w)\) contains both accepting and non-accepting states of \(M\) would be accepted both by \(M\) and by \(M'\text{.}\)

Now let’s turn to the question of intersection. Given two regular languages \(L_1\) and \(L_2\text{,}\) is \(L_1 \cap L_2\) regular? Again, it is useful to think in terms of DFAs: given machines \(M_1\) and \(M_2\) that accept \(L_1\) and \(L_2\text{,}\) can you use them to build a new machine that accepts \(L_1 \cap L_2\text{?}\) The answer is yes, and the idea behind the construction bears some resemblance to that behind the NFA-to-DFA construction. We want a new machine where transitions reflect the transitions of both \(M_1\) and \(M_2\) simultaneously, and we want to accept a string \(w\) only if that those sequences of transitions lead to final states in both \(M_1\) and \(M_2\text{.}\) So we associate the states of our new machine \(M\) with pairs of states from \(M_1\) and \(M_2\text{.}\) For each state \((q_1,q_2)\) in the new machine and input symbol \(a\text{,}\) define \(\delta((q_1,q_2),a)\) to be the state \((\delta_1(q_1,a), \delta_2(q_2,a))\text{.}\) The start state \(q_0\) of \(M\) is \((q_{01}, q_{02})\text{,}\) where \(q_{0i}\) is the start state of \(M_i\text{.}\) The final states of \(M\) are the the states of the form \((q_{f1}, q_{f2})\) where \(q_{f1}\) is an accepting state of \(M_1\) and \(q_{f2}\) is an accepting state of \(M_2\text{.}\) You should convince yourself that \(M\) accepts a string \(x\) iff \(x\) is accepted by both \(M_1\) and \(M_2\text{.}\)

The results of the previous section and the preceding discussion are summarized by the following theorem:

Theorem 17.4.14. Set Operations on Regular Languages.

The intersection of two regular languages is a regular language.
The union of two regular languages is a regular language.
The concatenation of two regular languages is a regular language.
The complement of a regular language is a regular language.
The Kleene closure of a regular language is a regular language.

Subsection 17.4.3 Non-regular Languages

The fact that our models for mechanical language-recognition accept exactly the same languages as those generated by our mechanical language-generation system would seem to be a very positive indication that in ``regular" we have in fact managed to isolate whatever characteristic it is that makes a language ``mechanical". Unfortunately, there are languages that we intuitively think of as being mechanically-recognizable (and which we could write C++ programs to recognize) that are not in fact regular.

How does one prove that a language is not regular? We could try proving that there is no DFA or NFA that accepts it, or no regular expression that generates it, but this kind of argument is generally rather difficult to make. It is hard to rule out all possible automata and all possible regular expressions. Instead, we will look at a property that all regular languages have; proving that a given language does not have this property then becomes a way of proving that that language is not regular.

Consider the language \(L = \{ w \in \{a,b\}^*| n_a(w) =2 \bmod{3}, n_b(w) = 2 \bmod{3} \}\text{.}\) Below is a DFA that accepts this language, with states numbered 1 through 9.

Diagram of DFA that accepts \(L = \{ w \in \{a,b\}^*| n_a(w) =2 \bmod{3}, n_b(w) = 2 \bmod{3} \}\) . — Figure 17.4.15.

Consider the sequence of states that the machine passes through while processing the string \(abbbabb\text{.}\) Note that there is a repeated state (state 2). We say that \(abbbabb\) ``goes through the state 2 twice", meaning that in the course of the string being processed, the machine is in state 2 twice (at least). Call the section of the string that takes you around the loop \(y\text{,}\) the preceding section \(x\text{,}\) and the rest \(z\text{.}\) Then \(xz\) is accepted, \(xyyz\) is accepted, \(xyyyz\) is accepted, etc. Note that the string \(aabb\) cannot be divided this way, because it does not go through the same state twice. Which strings can be divided this way? Any string that goes through the same state twice. This may include some relatively short strings and must include any string with length greater than or equal to 9, because there are only 9 states in the machine, and so repetition must occur after 9 input symbols at the latest.

More generally, consider an arbitrary DFA \(M\text{,}\) and let the number of states in \(M\) be \(n\text{.}\) Then any string \(w\) that is accepted by \(M\) and has \(n\) or more symbols must go through the same state twice, and can therefore be broken up into three pieces \(x,y,z\) (where \(y\) contains at least one symbol) so that \(w=xyz\) and

\(xz\) is accepted by \(M\)
\(xyz\) is accepted by \(M\) (after all, we started with \(w\) in \(L(M)\))
\(xyyz\) is accepted by \(M\)
etc.

Note that you can actually say even more: within the first \(n\) characters of \(w\) you must already get a repeated state, so you can always find an \(x,y,z\) as described above where, in addition, the \(xy\) portion of \(w\) (the portion of \(w\) that takes you to and back to a repeated state) contains at most \(n\) symbols.

So altogether, if \(M\) is an \(n\)-state DFA that accepts \(L\text{,}\) and \(w\) is a string in \(L\) whose length is at least \(n\text{,}\) then \(w\) can be broken down into three pieces \(x\text{,}\) \(y\text{,}\) and \(z\text{,}\) \(w=xyz\text{,}\) such that

\(x\) and \(y\) together contain no more than \(n\) symbols;
\(y\) contains at least one symbol;
1. \(xz\) is accepted by \(M\)
2. \(xyz\) is accepted by \(M\)
3. \(xyyz\) is accepted by \(M\)
4. etc.

The usually-stated form of this result is the Pumping Lemma:

Theorem 17.4.16. Pumping Lemma.

If \(L\) is a regular language and \(M\) is a DFA that accepts \(L\text{,}\) then there is some number \(n\gt 0\) such that any string \(w\) in \(L\) whose length is greater than or equal to \(n\) can be broken down into three pieces \(x\text{,}\) \(y\text{,}\) and \(z\text{,}\) \(w=xyz\text{,}\) such that

\(x\) and \(y\) together contain no more than \(n\) symbols;
\(y\) contains at least one symbol;
1. \(xz\) is accepted by \(M\)
2. \(xyz\) is accepted by \(M\)
3. \(xyyz\) is accepted by \(M\)
4. etc.

Though the Pumping Lemma says something about regular languages, it is not used to prove that languages are regular. It says ``if a language is regular, then certain things happen", not ``if certain things happen, then you can conclude that the language is regular." However, the Pumping Lemma is useful for proving that languages are not regular, since the contrapositive of ``if a language is regular then certain things happen" is ``if certain things don’t happen then you can conclude that the language is not regular." So what are the ``certain things"? Basically, the P.L. says that if a language is regular, there is some ``threshold" length for strings, and every string that goes over that threshold can be broken down in a certain way. Therefore, if we can show that ``there is some threshold length for strings such that every string that goes over that threshold can be broken down in a certain way" is a false assertion about a language, we can conclude that the language is not regular. How do you show that there is no threshold length? Saying a number is a threshold length for a language means that every string in the language that is at least that long can be broken down in the ways described. So to show that a number is not a threshold value, we have to show that there is some string in the language that is at least that long that cannot be broken down in the appropriate way.

Theorem 17.4.17.

\(\{ a^nb^n \ | \ n \geq 0 \}\) is not regular.

Proof.

We do this by showing that there is no threshold value for the language. Let \(N\) be an arbitrary candidate for threshold value. We want to show that it is not in fact a threshold value, so we want to find a string in the language whose length is at least \(N\) and which can’t be broken down in the way described by the Pumping Lemma. What string should we try to prove unbreakable? We can’t pick strings like \(a^{100}b^{100}\) because we’re working with an arbitrary \(N\) i.e. making no assumptions about \(N\)’s value; picking \(a^{100}b^{100}\) is implicitly assuming that \(N\) is no bigger than 200 --- for larger values of \(N\text{,}\) \(a^{100}b^{100}\) would not be ``a string whose length is at least \(N\)". Whatever string we pick, we have to be sure that its length is at least \(N\text{,}\) no matter what number \(N\) is. So we pick, for instance, \(w = a^Nb^N\text{.}\) This string is in the language, and its length is at least \(N\text{,}\) no matter what number \(N\) is. If we can show that this string can’t be broken down as described by the Pumping Lemma, then we’ll have shown that \(N\) doesn’t work as a threshold value, and since \(N\) was an arbitrary number, we will have shown that there is no threshold value for \(L\) and hence \(L\) is not regular. So let’s show that \(w = a^Nb^N\) can’t be broken down appropriately.

We need to show that you can’t write \(w = a^Nb^N\) as \(w=xyz\) where \(x\) and \(y\) together contain at most \(N\) symbols, \(y\) isn’t empty, and all the strings \(xz\text{,}\) \(xyyz\text{,}\) \(xyyyz\text{,}\) etc.\ are still in \(L\text{,}\) i.e. of the form \(a^nb^n\) for some number \(n\text{.}\) The best way to do this is to show that any choice for \(y\) (with \(x\) being whatever precedes it and \(z\) being whatever follows) that satisfies the first two requirements fails to satisfy the third. So what are our possible choices for \(y\text{?}\) Well, since \(x\) and \(y\) together can contain at most \(N\) symbols, and \(w\) starts with \(N\) \(a\)’s, both \(x\) and \(y\) must be made up entirely of \(a\)’s; since \(y\) can’t be empty, it must contain at least one \(a\) and (from (i)) no more than \(N\) \(a\)’s. So the possible choices for \(y\) are \(y=a^k\) for some \(1 \leq k \leq N\text{.}\) We want to show now that none of these choices will satisfy the third requirement by showing that for any value of \(k\text{,}\) at least one of the strings \(xz\text{,}\) \(xyyz\text{,}\) \(xyyyz\text{,}\) etc will not be in \(L\text{.}\) No matter what value we try for \(k\text{,}\) we don’t have to look far for our rogue string: the string \(xz\text{,}\) which is \(a^Nb^N\) with \(k\) \(a\)’s deleted from it, looks like \(a^{N-k}b^N\text{,}\) which is clearly not of the form \(a^nb^n\text{.}\) So the only \(y\)’s that satisfy (i) and (ii) don’t satisfy (iii); so \(w\) can’t be broken down as required; so \(N\) is not a threshold value for \(L\text{;}\) and since \(N\) was an arbitrary number, there is no threshold value for \(L\text{;}\) so \(L\) is not regular.

The fact that languages like \(\{a^nb^n\ | \ n \geq 0\}\) and \(\{a^p \ |\ p \text{ is prime}\}\) are not regular is a severe blow to any idea that regular expressions or finite-state automata capture the language-generation or language-recognition capabilities of a computer: They are both languages that we could easily write programs to recognize. It is not clear how the expressive power of regular expressions could be increased, nor how one might modify the FSA model to obtain a more powerful one. However, in the next chapter you will be introduced to the concept of a grammar as a tool for generating languages. The simplest grammars still only produce regular languages, but you will see that more complicated grammars have the power to generate languages far beyond the realm of the regular.

Exercises 17.4.4 Exercises

1.

Give a DFA that accepts the intersection of the languages accepted by the machines shown below. (Suggestion: use the construction discussed in the chapter just before Theorem 17.4.14.)

Diagram of two DFAs to combine. — Figure 17.4.18.

2.

Complete the proof of Theorem 17.4.1 by showing how to modify a machine that accepts \(L(r)\) into a machine that accepts \(L(r^*)\text{.}\)

3.

Using the construction described in Theorem 17.4.1, build an NFA that accepts \(L((ab\REOR a)^*(bb))\text{.}\)

4.

Prove that the reverse of a regular language is regular.

5.

Show that for any DFA or NFA, there is an NFA with exactly one final state that accepts the same language.

6.

Suppose we change the model of NFAs to allow NFAs to have multiple start states. Show that for any ``NFA" with multiple start states, there is an NFA with exactly one start state that accepts the same language.

7.

Suppose that \(M_1=(Q_1,\Sigma,q_1,\delta_1,F_1)\) and \(M_2=(Q_2,\Sigma,q_2,\delta_2,F_2)\) are DFAs over the alphabet \(\Sigma\text{.}\) It is possible to construct a DFA that accepts the langauge \(L(M_1)\cap L(M_2)\) in a single step. Define the DFA

\begin{equation*} M = (Q_1\times Q_2, \Sigma, (q_1,q_2), \delta, F_1\times F_2) \end{equation*}

where \(\delta\) is the function from \((Q_1\times Q_2)\times\Sigma\) to \(Q_1\times Q_2\) that is defined by: \(\delta((p1,p2),\sigma))=(\delta_1(p_1,\sigma),\delta_2(p_2,\sigma))\text{.}\) Convince yourself that this definition makes sense. (For example, note that states in \(M\) are pairs \((p_1,p_2)\) of states, where \(p_1\in Q_1\) and \(p_2\in Q_2\text{,}\) and note that the start state \((q_1,q_2)\) in \(M\) is in fact a state in \(M\text{.}\)) Prove that \(L(M)=L(M_1)\cap L(M_2)\text{,}\) and explain why this shows that the intersection of any two regular languages is regular. This proof---if you can get past the notation---is more direct than the one outlined above.

8.

Use the Pumping Lemma to show that the following languages over \(\ab\) are not regular.

\(\displaystyle L_1 = \{ x |n_a(x) = n_b(x)\}\)
\(\displaystyle L_2 = \{ xx | x \in \ab^*\}\)
\(\displaystyle L_3 = \{ xx^R | x \in \ab^*\}\)
\(\displaystyle L_4 = \{ a^nb^m | n \lt m \}\)

Prev Top Next