3.6. REFERENCES FOR CHAPTER 3 123

be folklore, this report deuionstrated how adding several other operations such as intersection or shuffle (See Exercise 7.3.4) makes the test fail, even though they do not extend the class of languages represeritable.

Even before developing UNIX, K. Thompson was investigating the use of regular expressions in commands such as grep, and his algorithm for processing such commands appears in [5]. The early development of UNIX produced several other commands that make heavy use of the extended regular-expression notation, such as M. Lesks lex command. A description of this command and other regular-expression techniques can be found in [1].

1. A, V, Aho, R, Sethi, and J. D, Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading MA, 1986.

2. J. L. Gischer, STAN-CS-TR-84-1033 (1984).

3. S, C. Kleenc, Representation of events in nerve nets and finite automata, In C. E. Shaimon and J. McCaithy, Automata Studies, Princeton Univ. Press, 1956, pp. 3-42.

4. R. McNaughton and H. Yamada, Regular expressions and state graphs for automata, IEEE Trans. Electronic Computers 9:1 (Jan., 1960), pp. 39-47.

5. K. Thompson, Regtilar expression search algorithm, Comm. ACM 11:6 (June, 1968), pp. 419-422.

Chapter 4

Properties of Regular Languages

The chapter explores the properties of regular languages. Our first tool for this exploration is a way to prove that certain languages are not regular. This theorem, called the pumping lemum, is introduced in Section 4.1.

One important kind of fact about the r(!gular languages is called a closure property. These properties let us build recognizers for languages that are constructed from other languages by certain operations. As an example, the intersection of two regular languages is also regnilar. Thus, given automata that recognize two different regular languages, we can construct mechanically an automaton that recognizes exactly the intersection of these two languages. Since the automaton for the intersection may have many more states than either of the two given automata, this closure property can be a useful tool for building complex automata. Section 2,1 used this construction in an essential way.

Sorne other important facts about regular languages are called decision properties. Our study of these properties gives us algorithms for answering important questions about automata. A central example is an algorithm for deciding whethcr two automata define the same language. A consequence of our ability to decide this question is that we can minimize automata, that is, fiud an equivalent to a given automaton that has as few states as possible. This problem has been important in the design of switching circuits for decades, since the cost of the circuit (area of a chip that the circuit occupies) tends to decrease as the number of states of the automaton implemented by the circuit decreases.

4.1 Proving Languages not to be Regular

We have established that the class of languages known as the regular languages has at least four different descriptions. They are the languages accepted by DFAs, by NFAs, and by e-NFAs; they are also the languages defined by regular expressions.

Not every language is a regular language. In this section, we shall introduce a powerful technique, known as the pumping lemma, for showing certain languages not to be rejgular. We then give several examples of nonregular languages. In Section 4.2 we; shall see how the pumping lemma can be used in tandem with closure properties of the regular languages to prove other languages iKtt to b(! regular.

4.1.1 The Pumping Lemma for Regular Languages

Let us Consider the language Loi - {0 1 n > 1}. This language contains all strings 01, ООП, 000111, and so on, that consist of one or more Os followed by an equal uumber of Ts. We claim that Lm is not a regular language. The intuitive argument is that if Lyi were regular, theu lqi would be the language of some DFA A. This automaton has some particular number of states, say к states, hnagirie tlus automaton receiving к Os aa input. It is in some state after consuming each of the к + 1 prefixes of the input: e,0,00,... ,0. Since there are oidy к different states, the pigeonhole principle tells us that after reading two different prefixes, say 0 and 0, A must be in the same state, say state q.

However, suppose instead that after reading i or j Os, the automaton A starts receiving Is as input. After receiving г Is, it must accept if it previously received i Os, but not if it received j Os, Since it was in state q when the Is started, it cfmnot remember whether it received г or j Os, so we can fool A and make it do the лvrong thing - accept if it should not, or fail to accept when it should.

The above argument is informal, but can be made precise. However, the same conclusion, that the language lqi is not regular, can be reached using a general result, as follows.

Theorem 4.1: (The pumping lemma for regular languages) Let L be a regular language. Then there exists a constant n (\vhich depends on L) such that for every string w in L such that ш > n, we can break w into three strings, w - xyz, sucli that:

1. yf.

2. \xy\ < n.

3. For all A; > 0, the string xyz is also in L.

That is, we can always find a nonempty string у not too far from the beginning oiw that can be pumped ; that is, repeating у any number of times, or deleting it (the case к - 0), keeps the resulting string in the language l.