Elements of the Theory of Computation

by Lewis, Harry; Papadimitriou, Christos H.

• ISBN13: 9780132624787
• ISBN10: 0132624788
• Edition: 2nd
• Format: Paperback
• Copyright: 1997-08-07
• Publisher: Pearson

Summary

Lewis and Papadimitriou present this long awaited Second Edition of their best-selling theory of computation. The authors are well-known for their clear presentation that makes the material accessible to a a broad audience and requires no special previous mathematical experience.In this new edition, the authors incorporate a somewhat more informal, friendly writing style to present both classical and contemporary theories of computation. Algorithms, complexity analysis, and algorithmic ideas are introduced informally in Chapter 1, and are pursued throughout the book. Each section is followed by problems.

Table of Contents

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