1.6 Summary of Chapter 1

♦ Finite Automata: Finite automHta involve states and transitions among states in response to inputs. They are iisefid for building several different kinds of software, including the lexical analysis component of a compiler and systems for verifying the correctness of circuits or protocols, for example.

4- Regular Expressions: These are a structural notation for describing the same patterns that can be represented by finite automata. They are used in many common types of software, including tools to search for patterns in text or in file names, for instance.

4- Context-Free Grammars: These are an important notation for describing the structure of programming languages and related sets of strings; they are used to build the parser component of a compiler.

4 Turing Machines: These are automata that model the power of real computers. They allow us to study decidabilty, the ciuestion of what can or cannot be done by a computer. They also let us distinguish tractable problems - those that can be solved in polynomial time - from the intractable problems - those that cannot.

f Deductive Proofs: This basic method of proof proceeds by listing statements that are either given to be true, or that follow logically from some of the previous statements.

4 Proving If-Then Statements: Many theorems are of the form if (something) then (something else). The .statement or statements following the if are the hypothesis, and what follows then is the conclusion. Deductive proofe of if-then statements begin with the hypothesis, and continue with statements that follow logically from the hypothesis and previous statements, until the conclusion is proved as one of the statements.

f Proving If-And-Only-If Statements: There are other theorems of the form (something) if and only if (something else). They are proved by showing if-then statements in both directions. A simUar kind of theorem claims the equality of the sets described in two different ways; these are proved by showing that each of the two sets is contained in the other.

Proving the Contrapositive: Sometimes, it is easier to prove a statement of the form if H then C by proving the equivalent .statement: if not G then not The latter is called the contrapositive of the former.

4 Proof by Contradiction: Other times, it is more convenient to prove the statement if Я then C by prodng if Я and not С then (something known to be false). A proof of this type is called proof by contradiction.

1.7. BEFERENCES FOR CHAPTER 1 35

-f Counterexamples: Sometiines we ai-e asked to show that a certain statement is not true. If tlie statement has one or more parameters, then we can show it is false as a generality by providing just one counterexample, that is, one assignment of values to the parameters that makes the statement false.

4 Inductive Proofs: A statement that has an integer parameter ri can often by proved by induction on n. We prove the statement is true for the basis, a finite number of cases for particular values of 7i, and then prove the inductive step: that if the statement is true for values up to n, then it is true fur n + 1.

f Structural Inductions: In some situations, including many in this book, the theorem to be proved inductively is about some recursively defined construct, such as trees. We may prove a theorem about the constructed objects by induction on the number of steps used in its construction. This type of induction is referred to as structural.

f Alpfiabets: An alphabet is any finite set of symbols.

4- Strings: .A string is a finite-length sequence of symbols,

f Languages and Problems: A language is a (possibly infinite) set of strings, all of which choose their symbols irom some one alphabet. When the strings of a language are to be interpreted in some way, the question of whether a string is in the language is sometimes called a problem.

1.7 References for Chapter 1

For extended coverage of the material of this chapter, including mathematical concepts underlying Computer Science, we recommend [1],

1. A. V. Aho and J, D. Ullman, Foundations of Computer Science, Computer Science Press, New York, 1994.

Chapter 2

Finite Automata

This chapter introduces the class of languages known as regular languages. These languages are exactly the ones that can be described by finite automata, which we sampled briefly in Section 1.1.1. After an extended example that will provide motivation for the study to follow, we define finite automata formally.

As was mentioned earlier, a finite automaton has a set of states, and its control moves from state to state in response to external hiputs. One of the crucial distinctions among classes of fiiute automata is whether that control is deterministic, meaning that the automaton cannot be in more than one state at any one time, or nondeterministic, meaning that it may be in several states at once. We shall discover that adding nondeterminisin does not let us define any language that cannot be defined by a deterministic finite automaton, but there can be substantial efficiency in describing an application using a nondeterministic automaton. In effect, nondetcrminism allows us to program solutions to problems using a higher-level language. The nondeterministic finite automaton is then compiled, by an algorithm we shall learn in this chapter, into a deterministic automaton that can be executed on a conventional computer.

We conclude the chapter with a study of an extended nondeterministic automaton that has the additional choice of making a transition from one state to another spontaneously, i.e., on the empty string as input. These automata also accept nothing but the regular languages. Howe\er, wo shall fiud them quite important in Chapter 3, when we study regular expressions and their equivalence to automata.

The study of the regular languages continues in Chapter 3. There, wc introduce another important way to describe regular languages: the algebraic notation known as regular expressions. After discussing regular expressions, and showing their equivalence to finite automata, we use both automata and regular expressions as tools in Chapter 4 to show certain important properties of the regular languages. Examples of such properties are the closure properties, which allow us to claim that one language is regular because one or more