Languages and Machines An Introduction to the Theory of Computer Science.pdf

Preface

The objective of the third edition of Languages and Machines: An Introduction to the

Theory of Computer Science remains the same as that of the first two editions, to provide

a mathematically sound presentation of the theory of computer science at a level suitable

for junior- and senior-level computer science majors. The impetus for the third edition was

threefold: to enhance the presentation by providing additional motivation and examples; to

expand the selection of topics, particularly in the area of computational complexity; and to

provide additional flexibility to the instructor in the design of an introductory course in the

theory of computer science.

While many applications-oriented students question the importance of studying the

oretical foundations, it is this subject that addresses the “big picture" issues of computer

science. When today’s programming languages and computer architectures are obsolete

and solutions have been found for problems currently of interest, the questions considered

in this book will still be relevant. What types of patterns can be algorithmically detected?

How can languages be formally defined and analyzed? What are the inherent capabilities

and limitations of algorithmic computation? What problems have solutions that require so

much time or memory that they are realistically intractable? How do we compare the relative

difficulty of two problems? Each of these questions will be addressed in this text.

Organization

Since most computer science students at the undergraduate level have little or no background

in abstract mathematics, the presentation is intended not only to introduce the foundations

of computer science but also to increase the student’s mathematical sophistication. This

is accomplished by a rigorous presentation of the concepts and theorems of the subject

accompanied by a generous supply of examples. Each chapter ends with a set of exercises

that reinforces and augments the material covered in the chapter.

To make the topics accessible, no special mathematical prerequisites are assumed.

Instead, Chapter 1 introduces the mathematical tools of the theory of computing; naive set

xiv Preface

theory, recursive definitions, and proof by mathematical induction. With the exception of

the specialized topics in Sections 1.3 and 1.4, Chapters 1 and 2 provide background material

that will be used throughout the text. Section 1.3 introduces cardinality and diagonalization,

which are used in the counting arguments that establish the existence of undecidable

languages and uncomputable functions. Section 1.4 examines the use of self-reference in

proofs by contradiction. This technique is used in undecidability proofs, including the proof

that there is no solution to the Halting Problem. For students who have completed a course

in discrete mathematics, most of the material in Chapter 1 can be treated as review.

Recognizing that courses in the foundations of computing may emphasize different

topics, the presentation and prerequisite structure of this book have been designed to permit

a course to investigate particular topics in depth while providing the ability to augment

the primary topics with material that introduces and explores the breadth of computer

science theory. The core material for courses that focus on a classical presentation of formal

and automata language theory, on computability and undecidability, on computational

complexity, and on formal languages as the foundation for programming language definition

and compiler design are given in the following table. A star next to a section indicates that

the section may be omitted without affecting the continuity of the presentation. A starred

section usually contains the presentation of an application, the introduction of a related

topic, or a detailed proof of an advanced result in the subject.

Formal Languages

Formal Language

Computability Computational for Programming

and Automata Theory Theory

Complexity

Languages

Chap. 1 : 1-3, 6 - 8

Chap. 1: all Chap. 1: all Chap. 1: 1-3, 6 - 8

Chap. 2: 1-3,4*

Chap. 2: 1-4

Chap. 3: 1-3,4*

Chap. 5: 1-6,7*

Chap. 5: 1-4,5-7* Chap. 3: 1-4

Chap. 4: 1-5,6 *, 7

Chap. 8 : 1-7, 8 '

Chap. 8 : 1-7, 8 * Chap. 4: 1-5,6 *. 7

Chap. 5: 1-6, 7*

Chap. 9: 1-5, 6 *

Chap. 9: l^t, 5-6* Chap. 5: 1-6, 7*

Chap. 6 : 1-5, 6 *

Chap. 10: 1 Chap. 11: 1-4, 5*

Chap. 7: 1-3,4-5*

Chap. 7: 1-5

Chap. 11: all Chap. 14: 1-4, 5-7* Chap. 18: all

Chap. 8 : 1-7, 8 *

Chap. 12: all Chap. 15: all

Chap. 19: all

Chap. 9: 1-5,6 *

Chap. 13: all

Chap. 16: 1-6, 7* Chap. 20: all

Chap. 10: all

Chap. 17: all

The classical presentation of formal language and automata theory examines the rela

tionships between the grammars and abstract machines of the Chomsky hierarchy. The com

putational properties of deterministic finite automata, pushdown automata, linear-bounded

automata, and Turing machines are examined. The analysis of the computational power of

abstract machines culminates by establishing the equivalence of language recognition by

Turing machines and language generation by unrestricted grammars.

Preface XV

Computability theory examines the capabilities and limitations of algorithmic prob

lem solving. The coverage of computability includes decidability and the Church-Turing

Thesis, which is supported by the establishment of the equivalence of Turing computabil

ity and ^-recursive functions. A diagonalization argument is used to show that the Halting

Problem for Turing machines is unsolvable. Problem reduction is then used to establish the

undecidability of a number of questions on the capabilities of algorithmic computation.

The study of computational complexity begins by considering methods for measuring

the resources required by a computation. The Turing machine is selected as the framework

for the assessment of complexity, and time and space complexity are measured by the

number of transitions and amount of memory used in Turing machine computations. The

class 7 of problems that are solvable by deterministic Turing machines in polynomial time

is identified as the set problems that have efficient algorithmic solutions. The class NT and

the theory of NP-completeness are then introduced. Approximation algorithms are used to

obtain near-optimal solutions for NP-complete optimization problems.

The most important application of formal language theory to computer science is the

use of grammars to specify the syntax of programming languages. A course with the focus

of using formal techniques to define programming languages and develop efficient parsing

strategies begins with the introduction of context-free grammars to generate languages

and finite automata to recognize patterns. After the introduction to language definition,

Chapters 18-20 examine the properties of LL and LR grammars and deterministic parsing

of languages defined by these types of grammars.

Exercises

Mastering the theoretical foundations of computer science is not a spectator sport; only by

solving problems and examining the proofs of the major results can one fully comprehend

the concepts, the algorithms, and the subtleties of the theory. That is, understanding the “big

picture” requires many small steps. To help accomplish this, each chapter ends with a set of

exercises. The exercises range from constructing simple examples of the topics introduced

in the chapter to extending the theory.

Several exercises in each set are marked with a star. A problem is starred because it

may be more challenging than the others on the same topic, more theoretical in nature, or

may be particularly unique and interesting.

Notation

The theory of computer science is a mathematical examination of the capabilities and lim

itations of effective computation. As with any formal analysis, the notation must provide

XVi Preface

precise and unambiguous definitions of the concepts, structures, and operations. The fol

lowing notational conventions will be used throughout the book:

Items Description Examples

Elements and strings

Italic lowercase letters from the beginning

of the alphabet

a, b, abc

Functions

Italic lowercase letters

f'g 'h

Sets and relations

Capital letters

X. Y.Z, z , r

Grammars

Capital letters

G, G„ G2

Variables of grammars

Italic capital letters

A, B, C, S

Abstract machines

Capital letters

M, M„M2

The use of roman letters for sets and mathematical structures is somewhat nonstandard

but was chosen to make the components of a structure visually identifiable. For example, a

context-free grammar is a structure G = (E , V, P, S). From the fonts alone it can be seen

that G consists of three sets and a variable S.

A three-part numbering system is used throughout the book; a reference is given by

chapter, section, and item. One numbering sequence records definitions, lemmas, theorems,

corollaries, and algorithms. A second sequence is used to identify examples. Tables, figures,

and exercises are referenced simply by chapter and number.

The end of a proof is marked by ■ and the end of an example by □ . An index of symbols,

including descriptions and the numbers of the pages on which they are introduced, is given

in Appendix I.

Supplements

Solutions to selected exercises are available only to qualified instructors. Please contact your

local Addison-Wesley sales representative or send email to aw.cse@aw.com for information

on how to access them.

Acknowledgments

First and foremost, I would like to thank my wife Janice and daughter Elizabeth, whose

kindness, patience, and consideration made the successful completion of this book possible.

I would also like to thank my colleagues and friends at the Institut de Recherche en

Informatique de Toulouse, Universite Paul Sabatier, Toulouse, France. The first draft of

this revision was completed while 1 was visiting IRIT during the summer of 2004. A special

thanks to Didier Dubois and Henri Prade for their generosity and hospitality.

The number of people who have made contributions to this book increases with each

edition. I extend my sincere appreciation to all the students and professors who have

剩余651页未读，继续阅读

Languages and Machines An Introduction to the Theory of Computer...

最新资源

Languages and Machines An Introduction to the Theory of Computer...

"探究形式语言与自动机：上下文无关文法与语言

"《Java编程思想》翻译与毕业设计指南

"学习计算机专业英语，提升阅读写作翻译能力 - 11/13/2022

Languages and Machines An Introduction to the Theory of Computer Science

An Introduction To The Theory Of Computation.pdf

A Concise Introduction to Languages and Machines.pdf

Introduction.to.Automata.Theory,.Languages,.and.Computation

introduction to languages theory of computation

Addison-Wesley - Introduction to Automata Theory, Languages and Computation Second Edition by Hopcroft, Motwani and Ullman.pdf

Introduction to Automata Theory Languages and Computation

最新资源