本書精辟地闡述了計(jì)算課程的入門理論，簡明地解釋了復(fù)雜的思想并且提供了堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)知識(shí)。作者提供了直觀的證明，同時(shí)避免過多數(shù)學(xué)細(xì)節(jié)，這樣學(xué)生就能夠集中精力理解基本理論。許多精心選擇的例子在幾種上下文中重復(fù)出現(xiàn)，這樣學(xué)生就能夠通過對(duì)比式的研究加強(qiáng)理解。
Peter Linz 在威斯康星大學(xué)獲得博士學(xué)位，是加州大學(xué)戴維斯分校計(jì)算機(jī)科學(xué)系退休教授，其研究領(lǐng)域?yàn)橛?jì)算機(jī)數(shù)值分析理論。除本書外，他還撰有《Exploring Numerical Methods:Fan Introduction to Scientific Computing》一書。
Chapter 1 Introduction to the Theory of Computation
1.1 Mathematical Preliminaries and Notation
1.2 Three Basic Concepts
1.3 Some Applications
Chapter 2 Finite Automata
2.1 Deterministic Finite Accepters
2.2 Nondeterministic Finite Accepter
2.3 Equivalence of deterministic and Nondeterminsitic Finite Accepters
2.4 Reduction of the Number of States in Finite Automata
Chapter 3 Regular Languages and Regular Grammars
3.1 Regular Expressions
3.2 Connection Between Regular Expressions and Regular Languages
3.3 Regular Grammars
Chapter 4 Properties of Regular Languages
4.1 Closure puoperties of Regular Languages
4.2 Elementary Questions about Regular Languages
4.3Identifying Nonregular Languages
Chapter 5 Context-Free Languages
Chapter 6 Simplification of Context-Free Grammars
Chapter 7 Pushdown Automata
Chapter 8 Puoperties of Context-Free Languages
Chapter 9 Turing Machines
Chapter 10 Other Models of Turing Machines
Chapter 11 A Hierarchy of Formal Languages and Automata
Chapter 12 Limits of Algorithmic Computation
Chapter 13 Other Models of Computation
Chapter 14 An Introduction to Computational Complexity
Answers to Selected Exercises
References
Index
