Automata and ComputabilityThe 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. |
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 |
389 | |
Other editions - View all
Common terms and phrases
accepts by empty algorithm automaton axioms binary bisimulation Chomsky computation concatenation configuration context-free languages corresponding DCFL defined definition denote derivation e-transitions empty stack encoding example exists external queue finite automata finite control finite set formal Give given grammar Greibach normal form halting problem Homework homomorphism induction hypothesis infinite input alphabet input string input symbol Kleene algebra left endmarker leftmost length loop marked Miscellaneous Exercise Myhill-Nerode relation Myhill-Nerode theorem natural numbers nondeterministic nondeterministic finite automaton nonterminal normal form NPDA number theory operator parse tree pebble productions proof provable Prove pumping lemma pushdown r.e. sets recursive set regular expression regular set reject Rice's theorem scanning sentential form set of strings simulate stack symbol step substring Supplementary Lecture T₂ tape transition function Turing machine unary undecidable
Popular passages
Page 376 - SA Greibach, A new normal form theorem for context-free phrase structure grammars.