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 MyhillNerode Relations. - 16 The MyhillNerode Theorem. - B Collapsing Nondeterministic Automata. - C Automata on Terms. - D The MyhillNerode 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 CockeKasamiYounger Algorithm. - G The ChomskySchü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 a-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 Sets. - Homework 1. - Homework 2. - Homework 3. - Homework 4. - Homework 5. - Homework 6. - Homework 7. - Homework 8. - Homework 9. - Homework 10. - Homework 11. - Homework 12. - Miscellaneous Exercises. - Finite Automata andRegular Sets. - Pushdown Automata and Context-Free Languages. - Turing Machines and Effective Computability. - Hints and Solutions. - Hints for Selected Miscellaneous Exercises. - Solutions to Selected Miscellaneous Exercises. - References. - Notation and Abbreviations. Language: English