These are my lecture notes from CS381/481: Automata and Computability Theory, a one-semester senior-level course I have taught at Cornell Uni­ versity for many years. I took this course myself in thc fall of 1974 as a first-year Ph.D. student at Cornell from Juris Hartmanis and have been in love with the subject ever sin,:e. The course is required for computer science majors at Cornell. It exists in two forms: CS481, an honors version; and CS381, a somewhat gentler­ paced version. The syllabus is roughly the same, but CS481 go es deeper into thc subject, covers more material, and is taught at a more abstract level. Students are encouraged to start off in one or the other, then switch within the first few weeks if they find the other version more suitaLle to their level of mathematical skill. The purpose of t.hc course is twofold: to introduce computer science students to the rieh heritage of models and abstractions that have arisen over the years; and to dew!c'p the capacity to form abstractions of their own and reason in terms of them.

Lectures.- 1 Course Roadmap and Historical Perspective.- 2 Strings and Sets.- 3 Finite Automata and Regular Sets.- 4 More on Regular Sets.- 5 Nondeterministic Finite Automata.- 6 The Subset Construction.- 7 Pattern Matching.- 8 Pattern Matching and Regular Expressions.- 9 Regular Expressions and Finite Automata.- A Kleene Algebra and Regular Expressions.- 10 Homomorphisms.- 11 Limitations of Finite Automata.- 12 Using the Pumping Lemma.- 13 DFA State Minimization.- 14 A Minimization Algorithm.- 15 Myhill-Nerode Relations.- 16 The Myhill-Nerode Theorem.- B Collapsing Nondeterministic Automata.- C Automata on Terms.- D The Myhill-Nerode Theorem for Term Automata.- 17 Two-Way Finite Automata.- 18 2DFAs and Regular Sets.- 19 Context-Free Grammars and Languages.- 20 Balanced Parentheses.- 21 Normal Forms.- 22 The Pumping Lemma for CFLs.- 23 Pushdown Automata.- E Final State Versus Empty Stack.- 24 PDAs and CFGs.- 25 Simulating NPDAs by CFGs.- F Deterministic Pushdown Automata.- 26 Parsing.- 27 The Cocke-Kasami-Younger Algorithm.- G The Chomsky-Schützenberger Theorem.- H Parikh's Theorem.- 28 Turing Machines and Effective Computability.- 29 More on Turing Machines.- 30 Equivalent Models.- 31 Universal Machines and Diagonalization.- 32 Decidable and Undecidable Problems.- 33 Reduction.- 34 Rice's Theorem.- 35 Undecidable Problems About CFLs.- 36 Other Formalisms.- 37 The ?-Calculus.- I While Programs.- J Beyond Undecidability.- 38 Gödel's Incompleteness Theorem.- 39 Proof of the Incompleteness Theorem.- K Gödel's Proof.- Exercises.- Homework 1.- Homework 2.- Homework 3.- Homework 4.- Homework 5.- Homework 6.- Homework 7.- Homework 8.- Homework 9.- Homework 10.- Homework 11.- Homework 12.- Finite Automata and Regular Sets.- Pushdown Automata andContext-Free Languages.- Turing Machines and Effective Computability.- Hints for Selected Miscellaneous Exercises.- Solutions to Selected Miscellaneous Exercises.- References.- Notation and Abbreviations.