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
鄂公网安备 42010302001612号 