计算理论基础（第2版）

　　内容简介随着计算机科学曰趋成熟并走向规范化，作为其甚础的计算理论的重要性也更加突出。作者根据本书第一版出版后使用中教师和学生的反馈意见和想法以及计算机科学的最新发展进行了修订。本书既讲述了经典的计算理论，又介绍了现代计算理论。全书共7章：1集、关系与语言，2有限自动机，3上下文无关文法语言，4.图灵机，5不可决定性，6计算复杂性，7.NP完全问题。本书适合于计算机系作本科生教材，也是一本难得的有关计算理论的参考书。

暂缺《计算理论基础（第2版）》作者简介

Preface to the First Edition                  
 Preface to the Second Edition                  
 Introduction                  
 1 Sets, Relations, and Languages                  
 1.1 Sets                  
 1.2 Relations and functions                  
 1.3 Special types of binary relations                  
 1.4 Finite and infinite sets                  
 1.5 Three fundamental proof techniques                  
 1.6 Closures and algorithms                  
 1.7 Alphabets and languages                  
 1.8 Finite representations of languages                  
 References                  
                   
 2 Finite Automata                  
 2.1 Deterministic finite automata                  
 2.2 Nondeterministic finite automata                  
 2.3 Finite automata and regular expressions                  
 2.4 Languages that are aJnd are not regular                  
 2.5 State minimization                  
 2.6 Algorithmic aspects of finite automata                  
 References                  
                   
 3 Cootext-free Languages                  
 3.1 Context-free grammars                  
 3.2 Parse trees                  
 3.3 Pushdown automata                  
 3.4 Pushdown automata and context-free grammars                  
 3.5 Languages that are and are not context-free                  
 3.6 Algorithms for context-free grammars                  
 3.7 Determinism and parsing                  
 References                  
                   
 4 Turing machines                  
 4.1 The definition of Turing machines                  
 4.2 Computing with Turing machines                  
 4.3 Extensions of Turing machines                  
 4.4 Random access Turing machines                  
 4.5 Nondeterministic Turing machines                  
 4.6 Grammars                  
 4.7 Numerical functions                  
 References                  
                   
 5 Undecidability                  
 5.1 The Church-Turing thesis                  
 5.2 Universal Turing machines                  
 5.3 The halting problem                  
 5.4 Unsolvable problems about Turing machines                  
 5.5 Unsolvable problems about grammars                  
 5.6 An unsolvable tiling problem                  
 5.7 Properties of recursive languages                  
 References                  
                   
 6 Computational Complexity                  
 6.1 The class P                  
 6.2 Problems, problems                  
 6.3 Boolean satisfiability                  
 6.4 The class NP                  
 References                  
                   
 7 NP-completeness                  
 7.1 Polynomial-time reductions                  
 7.2 Cook's Theorem                  
 7.3 More NP-complete problems                  
 7.4 Coping with NP-comp1eteness                  
 References                  
 Index