Problem Solving in Automata, Languages, and Complexity

by Du, Ding-Zhu; Ko, Ker-I

• ISBN13: 9780471439608
• ISBN10: 0471439606
• Edition: 1st
• Format: Hardcover
• Copyright: 2001-10-03
• Publisher: Wiley-Interscience

Summary

Automata and natural language theory are topics lying at the heart of computer science. Both are linked to computational complexity and together, these disciplines help define the parameters of what constitutes a computer, the structure of programs, which problems are solvable by computers, and a range of other crucial aspects of the practice of computer science. In this important volume, two respected authors/editors in the field offer accessible, practice-oriented coverage of these issues with an emphasis on refining core problem solving skills.

Author Biography

DING-ZHU DU, PhD, is Professor of Computer Science at the University of Minnesota.<BR>

Table of Contents

Preface	vii
Regular Languages	1	(22)
Strings and Languages	1	(7)
Regular Languages and Regular Expressions	8	(8)
Graph Representations for Regular Expressions	16	(7)
Finite Automata	23	(66)
Deterministic Finite Automata	23	(5)
Examples of Deterministic Finite Automata	28	(10)
Nondeterministic Finite Automata	38	(7)
Converting an NFA to a DFA	45	(8)
Finite Automata and Regular Expressions	53	(5)
Closure Properties of Regular Languages	58	(11)
Minimum Deterministic Finite Automata	69	(11)
Pumping Lemmas	80	(9)
Context-Free Languages	89	(70)
Context-Free Grammars	89	(10)
More Examples of Context-Free Grammars	99	(10)
Parsing and Ambiguity	109	(13)
Pushdown Automata	122	(10)
Pushdown Automata and Context-Free Grammars	132	(10)
Pumping Lemmas for Context-Free Languages	142	(17)
Turing Machines	159	(66)
One-Tape Turing Machines	159	(7)
Examples of Turing Machines	166	(14)
Multi-Tape Turing Machines	180	(11)
Church-Turing Thesis	191	(2)
Unrestricted Grammars	193	(7)
Primitive Recursive Functions	200	(6)
Pairing Functions and Godel Numberings	206	(8)
Partial Recursive Functions	214	(11)
Computability Theory	225	(56)
Universal Turing Machines	225	(7)
R. E. Sets and Recursive Sets	232	(9)
Diagonalization	241	(5)
Reducibility	246	(12)
Recursion Theorem	258	(8)
Undecidable Problems	266	(15)
Computational Complexity	281	(42)
Asymptotic Growth Rate	281	(5)
Time and Space Complexity	286	(11)
Hierarchy Theorems	297	(7)
Nondeterministic Turing Machines	304	(10)
Context-Sensitive Languages	314	(9)
NP-Completeness	323	(64)
NP	323	(16)
Polynomial-Time Reducibility	339	(11)
Cook's Theorem	350	(9)
More NP-Complete Problems	359	(11)
NP-Complete Optimization Problems	370	(17)
References	387	(2)
Index	389