Copyright ©1998-2010 Glenn Fleishman. Send in your comments. Bibliographic information on isbn.nu licensed from Baker & Taylor. Contact them for corrections and licensing, or read more about our data.
Tables of Contents for Elements of the Theory of Computation
Chapter/Section Title
Page #
Page Count
Preface to the First Edition
vii
2
Preface to the Second Edition
ix
Introduction
1
4
1 Sets, Relations, and Languages
5
50
1.1 Sets
5
4
1.2 Relations and functions
9
4
1.3 Special types of binary relations
13
7
1.4 Finite and infinite sets
20
3
1.5 Three fundamental proof techniques
23
7
1.6 Closures and algorithms
30
12
1.7 Alphabets and languages
42
5
1.8 Finite representations of languages
47
5
References
52
3
2 Finite Automata
55
58
2.1 Deterministic finite automata
55
8
2.2 Nondeterministic finite automata
63
12
2.3 Finite automata and regular expressions
75
11
2.4 Languages that are and are not regular
86
6
2.5 State minimization
92
10
2.6 Algorithmic aspects of finite automata
102
8
References
110
3
3 Context-free Languages
113
66
3.1 Context-free grammars
113
9
3.2 Parse trees
122
8
3.3 Pushdown automata
130
6
3.4 Pushdown automata and context-free grammars
136
7
3.5 Languages that are and are not context-free
143
7
3.6 Algorithms for context-free grammars
150
8
3.7 Determinism and parsing
158
17
References
175
4
4 Turing machines
179
66
4.1 The definition of a Turing machine
179
15
4.2 Computing with Turing machines
194
6
4.3 Extensions of Turing machines
200
10
4.4 Random access Turing machines
210
11
4.5 Nondeterministic Turing machines
221
6
4.6 Grammars
227
6
4.7 Numerical functions
233
10
References
243
2
5 Undecidability
245
30
5.1 The Church-Turing thesis
245
2
5.2 Universal Turing machines
247
4
5.3 The halting problem
251
3
5.4 Unsolvable problems about Turing machines
254
4
5.5 Unsolvable problems about grammars
258
4
5.6 An unsolvable tiling problem
262
5
5.7 Properties of recursive languages
267
5
References
272
3
6 Computational Complexity
275
26
6.1 The class P
275
3
6.2 Problems, problems
278
10
6.3 Boolean satisfiability
288
4
6.4 The class (NP)
292
7
References
299
2
7 NP-completeness
301
52
7.1 Polynomial-time reductions
301
8
7.2 Cook's Theorem
309
8
7.3 More (NP)-complete problems
317
16
7.4 Coping with (NP)-completeness
333
17
References
350
3
Index
353