Automata theory is the study of abstract computing devices, or machines. Before there were computers, in the 1930S, A. Turing studied an abstract machine that had all the capabilities of todays computers, at least as far as in what they could compute. Turings goal was to describe pre(:is Iy thf; boimdary between what a computing machine could do and what it could nut do; his conclusions apply not only to his abstract Turing machines, but to todays real machines.

In the 1940s and 19оОН; simpler khids of machines, which wc today call finite automata, were studied by a number of rraoarchers. These automata, originally proposed to model brain function, turned out to be extremely useful for a variety of other purposes, which wc sliiUl mention in Section 1.1. Also in the late 1950s, the linguist N. Chomsky began the study of formal grammars. While not strictly machines, th(;so grannnars have close relationshij).s to abstract automata and scjrvc today as the basis of sonic important .soft.waro components, including parts of <:om])ik;rs.

In 1969, S. Cook extended Turings .study of what could and what could not be computed. Cook Wiis able to separate those problems that can hv. solved efficiently by computer from those problems that can in prmciplc be solved, but in practice take so nmch time that computers are useless for all but \ery small instances of the problem. Ttie latter class of problems is called intractable, or NP-hard. It is highly unlikely that even the exponential improvement in computing speed that computer liardwaie has been following ( Moores Law ) will have significant impact on our ability to solve lai-g(! instances of intractable problems.

All of these theoretical developments bear directly on what computer scientists do today. Some of the concepts, like finite automata and certain kinds of formal grammars, are used in the design and construction of important kinds of software. Other concepts, like the Turing machine, help us understand what

we сал ex]>f!Ct from o\ir software. Especially; the theory of intractable problems lets us deduco whether we are likely to be able to meet a problem head-on and writo a program to solve it {because it is not in the intractable class), or whether wo have to find some way to work around the intractable problem: find an approximation, use a heiiristic, or use some other method to hmit the amount of time the program will spend solving the problem.

In this introductory chapter, we begin with a very high-level view of what automata theory is about, and what its uses are. Much of the chapter is devoted to a survey of proof techniques and tricks for liiscovering proofs. We cover deductive proofs, reformulating statements, proofs by contradiction, proofs by induction, and other important concepts. A final section introduces the concepts that pervade automata theory: alphabets, strings, and languages.

1.1 Why Study Automata Theory?

There are sevc<ral reasons why the study of automata and complexity is an important part of the core of Computer Science. This section serves to introduco the rcfider to the principal motivation and also outlines the major topics covered in this book.

1Л.1 Introduction to Finite Automata

Finite automata are a useful model for many important lands of hardware and software. We shall see, starting in Chapter 2. examples of liow the cwncepts are used. For the moment, let us just list some of the most important kinds;

1. Software for designing and checking the behavior of digital circuits.

2. The lexical analyzer of a typical compiler, that is, the compiler component that breaks the input text into logical units, such as identifiers, keywords, and punctuation.

3. Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases, or other patterns.

4. Software for verifying ssystems of all types that have a finite number of distinct states, such as communications protocols or jjrotocols for secure exchange of information.

While we sliall soon meet a precise definition of automata of various types, let us begin our informal introduction with a sketch of what a finite automaton is and does. There are many systems or components, such as those enumerated above, that may be viewed as being at all times in one of a finite nunaber of states.- The purpose of a state is to remember the relevant portion of the systems history. Since there are only a Snito number of states, the entire history generally cannot be remembered, so the system must be designed carefully, to

LI. WHY STUDY AUTOMATA THEORY? 3

remember what is important and forget what is not. The advantage of having only a finite number of states is that we can implement the system with a fixed set of resources. For example, we could implement it in hardware as a circuit, or as a simple form of program that can make decisions looking only at a limited amount of data or using the position in the code itself to make the decision.

Example ХЛ: Perhaps the simplest nontrivial finite automaton is an on/off switch. The device remembers whether it is in the on state or the off state, and it allows the user to press a button whose effect is different, depending on the state of the switch. That is, if the switch is in the off state, then pressing the button changes it to the on state, and if the switch is in the on state, then pressing the same button turns it to the off state.

Push

-off 1 (on)

Push

Figure 1.1: A finite automaton modeling an on/off switch

The finite-automaton model for the sw-itch is shown in Fig. 1,1. As for all finite automata, the states are represented by circles; in this example, we have named the states on and off. Arcs between states are labeled by inputs, which represent external infiuences on the system. Here, both arcs are labeled by the input Push, which represents a user pushing the button. Tlie intent of the two arcs is that wlrichever state the system is in, when the Push input is received it goes to the other state.

One of the states is designated the start state, the state in which the system is placed initially. In our example, the start state is off, and we conventionally indicate the start state by the word Start and an arrow leading to that state.

It is often necessary to indicate one or more states as final or accepting states. Entering one of these states after a sequence of inputs indicates that the input sequence is good in some way. For instance, we could have regarded the state on in Fig. 1,1 as accepting, because in that state, the device being controlled by the switch will operate. It is conventional to designate accepting states by a double circle, although we have not made any such designation in Fig. 1,1. □

Example 1.2 : Sometimes, what is remembered by a state can be much more complex than an on/ofF choice. Figure 1.2 shows another finite automaton that could be part of a lexical analyzer. The job of this automaton is to recognize