MODULE 1

1.1. WHY STUDY AUTОМАТА 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 1.1: 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

Start
off on

Push

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

The finite-automaton model for the switch is shown in Fig. 1.1. As for all
finite automata, thestates 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 influences on the system. Here, both arcs are labeled by the
input Push, which represents a user pushing the button. The intent of the two
arcs is that whichever state the system is in, when the Push input is received
it goes to the other state.
One of the designated the "start state," the state in which the
states is
system is placed initially. In our example, the start state is off, and we conven-
tionally 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 asequence 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
4 CHAPTER 1. AUTOMATA: THE МЕТНОDS AND THE MADNESS

the keyword then. It thus needs five states, each of which representsadifferent
position in the word then that has been reached so far. These positions corre-
spond to the prefixes of the word, ranging from the empty string (i.e., nothing
of the word has been seen so far) to the complete word.

Start t h e n

t th the (then

Figure 1.2: A finite automaton modeling recognition of then

In Fig. 1.2, the five states named by the prefix of then scen so far. Inputs
are

correspond to letters. We may imagine that the lexical analyzer examincs one
character of the program that it is compiling at a time, and the next character
to be exanined is the input to the automaton. The start state corresponds to

the empty string, and each state has a transition on the next letter of then to
the state that corresponds to the next-larger prefix. The state named then is
entered when the input has spelled the word then. Since it is the job of this
automaton to recognize when then has been seen, we could consider that state
the lone accepting state. ☐

1.1.2 Structural Representations

There are two important notations that are not automaton-like, but play an

important role in the study of automata and their applications.

1. Grammars are useful models when designing software that processes data
with a recursive structure. The best-known example is a "parser," the
component of a compiler that deals with the recursively nested features

of the typical programming language, such as expressions arithmetic,

-

conditional, and so on. For instance, a grammatical rule like E⇒ E+E

states that an expression can be formed by taking any two expressions
and connecting them by a plus sign; this rule is typical of how expressions
of real programming languages are formed. We introduce context-free
grammars, as they are usually called, in Chapter 5.

2. Regular Expressions also denote the structure of data, especially text

strings. As we shall see in Chapter 3, the patterns of strings they describe
are exactly the same as what can be described by finite automata. The
style expressions differs significantly from that of grammars, and
of these
we shall content ourselves witha simple example here. The UNIX-style

regular expression ' [A-Z] [a-z]*[ ] [A-Z] [A-Z]' represents capitalized

words followed by a space and two capital letters. This expression rep-
resents patterns in text that could be a city and state, e.g., Ithaca NY.
It misses multiword city names, such as Palo Alto CA, which could be
captured by the more complex expression
1.2. INTRODUCTION TO FORMAL PROOF 5

'([A-Z] [a-z]*[ ])*[ ] [A-Z] [A-Z]

When interpreting such expressions, only need to know that [A-Z]

we

represents a range of characters from to capital "Z" (i.e., any

capital "A"
capital letter), and [ ] is used to represent the blank character alone.
Also, the symbol * represents "any number of" the preceding expression.
Parentheses are used to group components of the expression; they do not
represent characters of the text described.

1.1.3 Automata and Complexity

Automata are essential for the study of the limits of computation. As we

mentioned in the introduction to the chapter, there are two important issues:

1. What can a computer do at all? This study is called "decidability," and

the problems that can be solved by computer are called "decidable." This
topic is addressed in Chapter 9.

2. What can a computer do efficiently? This study is called "intractabil-

ity," and the problems that can be solved by a computer using no more
time than some slowly growing function of the size of the input are called
"tractable." Often, we take all polynomial functions to be "slowly grow-

ing," while functions that grow faster than any polynomial are deemed to
grow too fast. The subject is studied in Chapter 10.

1.2 Introduction to Formal Proof

If you studied plane geometry in high school any time before the 1990's, you
most likely had to do some detailed "deductive proofs," where you showed
the truth of a statement by a detailed sequence of steps and reasons. While
geometry has its practical side (e.g., you need to know the rule for computing
the area rectangle if you need to buy the correct amount of carpet for a
of a

room), the study of formal proof methodologies was at least as important a

reason for covering this branch of mathematics in high school.

In the USA of the 1990's it became popular to teach proof as a matter

of personal feelings about the statement. While it is good to feel the truth
of a statement you need to use, important techniques of proof are no longer
mastered in high school. Yet proof is something that every computer scientist
needs to understand. Some computer scientists take the extreme view that a
formal proof of the correctness of a program should go hand-in-hand with the
writing of the program itself. We doubt that doing so is productive. On the
other hand, there are those who say that proof has no place in the discipline of
programming. The slogan "if you are not sure your program is correct, run it
and see" is commonly offered by this camp.
28 СHАРТER 1. AUTOMATA: THЕ МЕТНODS AND THE MADNESS

1. [S(n+1); If] The hypothesis for this part is that n+1 is even. Thus,
n is odd. The "if" part of statement S2(n) says that after n pushes, the
automaton is in state on. The arc from on to off labeled Push tells us
that the(n +1)st push will cause the automaton to enter state off. That
completes the proof of the "if" part of S₁(n + 1).

2. [S1(n+1); Only-if] The hypothesis is that the automaton is in state off

after n+1 pushes. Inspecting the automaton of Fig. 1.8 tells us that the
only way to get to state off after one or more moves is to be in state on and
receive an input Push. Thus, if we are in state off after n + 1 pushes, we
must have been in state on after n pushes. Then, we may use the "only-if"
part of statement 52(n) to conclude that n is odd. Consequently, n+1 is
even, which is the desired conclusion for the only-if portion of S1(n +1).

3. [S2(n+1); If] This part is essentially the same as part (1), with the roles of
statements S1 and S2 exchanged, and with the roles of "odd" and "even"
exchanged. The reader should be able to construct this part of the proof
easily.

4. [S2(n+1); Only-if] This part is essentially the same as part (2), with the
roles of statements S1 and S2 exchanged, and with the roles of "odd" and
"even" exchanged.

We can abstract from Example 1.23 the pattern for all mutual inductions:

•
Each of the statements must be proved separately in the basis and in the
inductive step.

이
If the statements are "if-and-only-if," then both directions of each state-
ment must be proved, both in the basis and in the induction.

1.5 The Central Concepts of Automata Theory

In this section we shall introduce the most important definitions of terms that
pervade the theory of automata. These concepts include the "alphabet" (a set
of symbols), "strings" (a list of symbols from an alphabet), and "language" (a
set of strings from the same alphabet).

1.5.1 Alphabets
An alphabet is a finite, nonempty set of symbols. Conventionally, we use the
symbol Σ for an alphabet. Common alphabets include:

1. Σ = {0, 1}, the binary alphabet.