Automata and Computability

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

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.

References to this book

 Engineering a CompilerLimited preview - 2004
 Graph Algebras and AutomataAndrei KelarevLimited preview - 2003
All Book Search results &raquo;