Automata and Computability

Front Cover
Springer Science & Business Media, Jun 29, 2007 - Computers - 400 pages
The aim of this textbook is to provide undergraduate students with an introduction to the basic theoretical models of computability, and to develop some of the model's rich and varied structure. Students who have already some experience with elementary discrete mathematics will find this a well-paced first course, and a number of supplementary chapters introduce more advanced concepts. The first part of the book is devoted to finite automata and their properties. Pushdown automata provide a broader class of models and enable the analysis of context-free languages. In the remaining chapters, Turing machines are introduced and the book culminates in discussions of effective computability, decidability, and Gödel's incompleteness theorems. Plenty of exercises are provided, ranging from the easy to the challenging. As a result, this text will make an ideal first course for students of computer science.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Course Road map and Historical Perspective
3
Strings and Sets
7
Finite Automata and Regular Sets
14
More on Regular Sets
19
Nondeterministic Finite Automata
25
The Subset Construction
32
Pattern Matching
40
Pattern Matching and Regular Expressions
44
More on Turing Machines
215
Equivalent Models
221
Universal Machines and Diagonalization
228
Decidable and Undecidable Problems
235
Reduction
239
Rices Theorem
245
Undecidable Problems About CFLs
249
Other Formalisms
256

Regular Expressions and Finite Automata
49
Kleene Algebra and Regular Expressions
55
Homomorphisms
61
Limitations of Finite Automata
67
Using the Pumping Lemma
72
DFA State Minimization
77
A Minimization Algorithm
84
MyhillNerode Relations
89
The MyhillNerode Theorem
95
Collapsing Nondeterministic Automata
100
Automata on Terms
108
The MyhillNerode Theorem for Term Automata
114
TwoWay Finite Automata
119
2DFAs and Regular Sets
124
ContextFree Grammars and Languages
129
Balanced Parentheses
135
21 Normal Forms
140
The Pumping Lemma for CFLs
148
Pushdown Automata
157
Final State Versus Empty Stack
164
PDAs and CFGs
167
Simulating NPDAs by CFGs
172
Deterministic Pushdown Automata
176
Parsing
181
The CockeKasamiYounger Algorithm
191
The ChomskySchutzenberger Theorem
198
Parikhs Theorem
201
Turing Machines and Effective Computability
206
The ACalculus
262
While Programs
269
Beyond Undecidability
274
Godels Incompleteness Theorem
282
Proof of the Incompleteness Theorem
287
Godels Proof
292
Exercises
299
Homework 1
301
Homework 2
302
Homework 3
303
Homework 4
304
Homework 5
306
Homework 6
307
Homework 7
308
Homework 8
309
Homework 9
310
Homework 10
311
Homework 11
312
Homework 12
313
Finite Automata and Regular Sets
315
Pushdown Automata and ContextFree Languages
333
Turing Machines and Effective Computability
340
Hints for Selected Miscellaneous Exercises
351
Solutions to Selected Miscellaneous Exercises
357
References
373
Notation and Abbreviations
381
Index
389
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 376 - SA Greibach, A new normal form theorem for context-free phrase structure grammars.
Page 379 - MY Vardi. A note on the reduction of two-way automata to one-way automata. Information Processing Letters, 30(5):261-264, 1989.
Page 373 - W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Annalen 99 (1928), S.
Page 373 - RC Backhouse. Closure Algorithms and the StarHeight Problem of Regular Languages. PhD thesis, Imperial College, 1975.
Page 379 - ... Syntactic Analysis and the Pushdown Store," Proceedings of Symposia on Applied Mathematics (Vol. 12). Providence, RI: American Mathematical Society, 1961. Theorem 3.4.1 on the equivalence of context-free languages and pushdown automata was proved independently by Schutzenberger, Chomsky, and Evey. MP SCHUTZENBERGER, "On Context-free Languages and Pushdown Automata," Information and Control, 6, no. 3 (1963), 246-264. N. CHOMSKY, "Context-free Grammar and Pushdown Storage," Quarterly Progress Report,...
Page 379 - A. YASUHARA, Recursive Function Theory and Logic, Academic Press, New York, 1971.

Bibliographic information