自动机理论、语言和计算导论（第2版）（英文影印版）
点击看大图基本信息
- 作者： John E.Hopcroft,Rajeev Motwani,Jeffrey D.Ullman
- 丛书名： 大学计算机教育国外著名教材、教参系列（影印版）
- 出版社：清华大学出版社
- ISBN：730205021X
- 上架时间：2002-7-9
- 出版日期：2002 年6月
- 页码：540
- 版次：1-1
- 所属分类：
计算机 > 计算机科学理论与基础知识 > 计算理论 > 自动机
教材 > 研究生/本科/专科教材 > 工学 > 计算机
教材 > 计算机教材 > 本科/研究生 > 计算机专业教材 > 计算机基础课程 > 算法与数学基础
内容简介回到顶部↑
本书是一本有关自动机理论、形式语言和计算复杂性的经典著作。第2版出版时，主要供研究生教学使用。由于自动机和语言理论在计算机科学的教育中已成为本科生的主要课程，作者在第2版的基础上作了全面修订。本书（第2版）除了继承原书“外看大，内看小”的特点外，在内容和风格上都作了很大的调整：降低了数学上的难度，删除了一些应用背景不大的内容，增加了一些在实践中较有影响的例子，把相关内容成功地纳入了本科阶段的教育体系。本书主要内容包括：有限状态自动机，正规语言，正规表达式，上下文无关文法，上下文无关语言，下推自动机，图灵机以及问题的不可解性、难解性和复杂性。每节后都附有练习。本书适合作计算机科学相关专业高年级教学用书。
作译者回到顶部↑
目录回到顶部↑
1 automata: the methods and the madness
1.l why study automata theory?
1.1.1 introduction to finite automata
1.1.2 structural representations
1.1.3 automata and complexity
1.2 introduction to formal proof
1.2.1 deductive proofs
1.2.2 reduction to definitions
1.2.3 other theorem forms
1.2.4 theorems that appear not to be if then statements
1.3 additional forms of proof
1.3.1 proving equivalences about sets
1.3.2 the contrapositive
1.3.3 proof by contradiction
1.3.4 counterexamples
1.4 inductive proofs
1.4.1 inductions on integers
1.4.2 more general forms of integer inductions
1.4.3 structural inductions
1.4.4 mutual inductions
1.l why study automata theory?
1.1.1 introduction to finite automata
1.1.2 structural representations
1.1.3 automata and complexity
1.2 introduction to formal proof
1.2.1 deductive proofs
1.2.2 reduction to definitions
1.2.3 other theorem forms
1.2.4 theorems that appear not to be if then statements
1.3 additional forms of proof
1.3.1 proving equivalences about sets
1.3.2 the contrapositive
1.3.3 proof by contradiction
1.3.4 counterexamples
1.4 inductive proofs
1.4.1 inductions on integers
1.4.2 more general forms of integer inductions
1.4.3 structural inductions
1.4.4 mutual inductions
前言回到顶部↑
In the preface from the 1979 predecessor to this book, Hopcroft and Ullman marveled at the fact that the subject of automata had exploded, compared with its state at the time they wrote their first book, in 1969. Truly, the 1979 book contained many topics not found in the earlier work and was about twice its size. If you compare this book with the 1979 book, you will find that, like the automobiles of the 1970's, this book is "larger on the outside, but smaller on the inside." That sounds like a retrograde step, but we axe happy with the changes for several reasons.
First, in 1979, automata and language theory was still an area of active research. A purpose of that book was to encourage mathematically inclined students to make new contributions to the field. Today there is little direct research in automata theory (as opposed to its applications), and thus little motivation for us to retain the succinct, highly mathematical tone of the 1979 book.
Second, the role of automata and language theory has changed over the past two decades. In 1979, automata was largely a graduate-level subject, and we imagined our reader was an advanced graduate student, especially those using the later chapters of the book. Today, the subject is a staple of the undergraduate curriculum. As such, the content of the book must assume less in the way of prerequisites from the student, and therefore must provide more of the background and details of arguments than did the earlier book.
A third change in the environment is that Computer Science has grown to an almost unimaginable degree in the past two decades. While in l979 it was often a challenge to fill up a curriculum with material that we felt would survive the next wave of technology, today very many subdisciplil1es compete for the limited amount of space in the undergraduate curriculum.
Fourthly, CS has become a more vocational subject, and there is a severe pragmatism among many of its students. We continue to be1ieve that aspects of automata theory axe essential tools in a variety of new disciplines, and we believe that the theoretical, mind-expanding exercises embodied in the typical automata course retain their value, no matter how much the student prefers to learn only the most immediately monetizable technology However, to assure a continued place for the subject on the menu of topics available to the computer science student, we believe it is necessary to emphasize the applications along with the mathematics. Thus, we have replaced a number of the more abstruse topics in the earlier book with examples of how the ideas are used today. While applications of automata and language theory to compilers are now so well understood that they are normally covered in a compiler course, there are a variety of more recent uses, including model-checking algorithms to verify protocols and document-description languages that are patterned on context-free grammars.
A final explanation for the simultaneous growth and shrinkage of the book is that we were today able to take advantage of the TEX and LATEX typesetting systems developed by Don Knuth and Les Lamport. The latter, especially, encourages the "open" style of typesetting that makes books larger, but easier to read. We appreciate the efforts of both men.
Use of the Book
This book is suitable for a quarter or semester course at the Junior level or above. At Stanford, we have used the notes in CS154, the course in automata and language theory It is a one-quarter course，which both Rajeev and Jeff have taught. Because of the limited time available, Chapter 11 is not covered, and some of the later material, such as the more difficult polynomial-time reductions in Section 10.4 are omitted as well. The book's Web site (see below) includes notes and syllabi for several offerings of CS154.
Some years ago, we found that many graduate students came to Stanford with a course in automata theory that did not include the theory of intractability. As the Stanford faculty believes that these ideas are essential for every computer scientist to know at more than the level of "NP-complete means it takes too long," there is another course, CS154N, that students may take to cove only Chapters 8, 9, and 10. They actually participate in roughly the last third of CS154 to fulfill the CS154N requirement. Even today, we find several students each quarter availing themselves of this option. Since it requires little extra effort, we recommend the approach.
Prerequisites
To make best use of this book, students should have taken previously a course covering discrete mathematics, e.g., graphs, trees, logic, and proof techniques. We assume also th8t they have had several courses in programming, and are familiar with common data structures, recursion, and the role of major system components such as compilers. These prerequisites should be obtained in a typical freshman-sophomore CS program.
Exercises
The book contains extensive exercises, with some for almost every section. We indicate harder exercises or parts of exercises with an exclamation point. The hardest exercises have a double exclamation point.
Some of the exercises or parts axe marked with a star. For these exercises, we shall endeavor to maintain solutions accessible through the book's Web page. These solutions are publicly available and should be used for self testing. Note that in a few cases, one exercise B asks for modification or adaptation of your solution to another exercise A. If certain parts of A have solutions, then you should expect the corresponding parts of B to have solutions as well.
Support on the world Wide Web
The book's home page is http: //www-db. stanford. edu/~ul1man/ia1c. html Here are solutions to starred exercises, errata as we learn of them, and backup materials. We hope to make available the notes for each offering of CS154 as we learn it, including homeworks, solutions, and exams.
Acknowledgements
A handout on "how to do proofs" by Craig Silverstein influenced some of the material in Chapter 1. Comments and errata on drafts of this book were received from: Zoe Abrams, George Candea, Haowen Chen, Byong-Gun Chun, Jeffrey Shallit, Bret Taylor, Jason Townsend, and Erik Uzureau. They are gratefully acknowledged. Remaining errors are ours,of course.
J. E. H.
R. M.
First, in 1979, automata and language theory was still an area of active research. A purpose of that book was to encourage mathematically inclined students to make new contributions to the field. Today there is little direct research in automata theory (as opposed to its applications), and thus little motivation for us to retain the succinct, highly mathematical tone of the 1979 book.
Second, the role of automata and language theory has changed over the past two decades. In 1979, automata was largely a graduate-level subject, and we imagined our reader was an advanced graduate student, especially those using the later chapters of the book. Today, the subject is a staple of the undergraduate curriculum. As such, the content of the book must assume less in the way of prerequisites from the student, and therefore must provide more of the background and details of arguments than did the earlier book.
A third change in the environment is that Computer Science has grown to an almost unimaginable degree in the past two decades. While in l979 it was often a challenge to fill up a curriculum with material that we felt would survive the next wave of technology, today very many subdisciplil1es compete for the limited amount of space in the undergraduate curriculum.
Fourthly, CS has become a more vocational subject, and there is a severe pragmatism among many of its students. We continue to be1ieve that aspects of automata theory axe essential tools in a variety of new disciplines, and we believe that the theoretical, mind-expanding exercises embodied in the typical automata course retain their value, no matter how much the student prefers to learn only the most immediately monetizable technology However, to assure a continued place for the subject on the menu of topics available to the computer science student, we believe it is necessary to emphasize the applications along with the mathematics. Thus, we have replaced a number of the more abstruse topics in the earlier book with examples of how the ideas are used today. While applications of automata and language theory to compilers are now so well understood that they are normally covered in a compiler course, there are a variety of more recent uses, including model-checking algorithms to verify protocols and document-description languages that are patterned on context-free grammars.
A final explanation for the simultaneous growth and shrinkage of the book is that we were today able to take advantage of the TEX and LATEX typesetting systems developed by Don Knuth and Les Lamport. The latter, especially, encourages the "open" style of typesetting that makes books larger, but easier to read. We appreciate the efforts of both men.
Use of the Book
This book is suitable for a quarter or semester course at the Junior level or above. At Stanford, we have used the notes in CS154, the course in automata and language theory It is a one-quarter course，which both Rajeev and Jeff have taught. Because of the limited time available, Chapter 11 is not covered, and some of the later material, such as the more difficult polynomial-time reductions in Section 10.4 are omitted as well. The book's Web site (see below) includes notes and syllabi for several offerings of CS154.
Some years ago, we found that many graduate students came to Stanford with a course in automata theory that did not include the theory of intractability. As the Stanford faculty believes that these ideas are essential for every computer scientist to know at more than the level of "NP-complete means it takes too long," there is another course, CS154N, that students may take to cove only Chapters 8, 9, and 10. They actually participate in roughly the last third of CS154 to fulfill the CS154N requirement. Even today, we find several students each quarter availing themselves of this option. Since it requires little extra effort, we recommend the approach.
Prerequisites
To make best use of this book, students should have taken previously a course covering discrete mathematics, e.g., graphs, trees, logic, and proof techniques. We assume also th8t they have had several courses in programming, and are familiar with common data structures, recursion, and the role of major system components such as compilers. These prerequisites should be obtained in a typical freshman-sophomore CS program.
Exercises
The book contains extensive exercises, with some for almost every section. We indicate harder exercises or parts of exercises with an exclamation point. The hardest exercises have a double exclamation point.
Some of the exercises or parts axe marked with a star. For these exercises, we shall endeavor to maintain solutions accessible through the book's Web page. These solutions are publicly available and should be used for self testing. Note that in a few cases, one exercise B asks for modification or adaptation of your solution to another exercise A. If certain parts of A have solutions, then you should expect the corresponding parts of B to have solutions as well.
Support on the world Wide Web
The book's home page is http: //www-db. stanford. edu/~ul1man/ia1c. html Here are solutions to starred exercises, errata as we learn of them, and backup materials. We hope to make available the notes for each offering of CS154 as we learn it, including homeworks, solutions, and exams.
Acknowledgements
A handout on "how to do proofs" by Craig Silverstein influenced some of the material in Chapter 1. Comments and errata on drafts of this book were received from: Zoe Abrams, George Candea, Haowen Chen, Byong-Gun Chun, Jeffrey Shallit, Bret Taylor, Jason Townsend, and Erik Uzureau. They are gratefully acknowledged. Remaining errors are ours,of course.
J. E. H.
R. M.
加载中...
