Dr. BakerFall 200?Table of ContentsI. Lecture NotesA. Overview and Introduction1. The Three Hour Tour Through Automata Theory2. What is a Language?B. Regular Languages and Finite State Machines1. Regular Languages2. Finite State Machines3. Nondeterministic Finite State Machines4. Interpreters for Finite State Machines5. Equivalence of Regular Languages and FSMs6. Languages that Are and Are Not Regular7. A Review of Equivalence Relations8. State Minimization9. Summary of Regular Languages and Finite State MachinesC. Context-Free Languages and Pushdown Automata1. Context Free Grammars2. Parse Trees3. Pushdown Automata4. Pushdown Automata and Context-Free Languages5. Grammars and Normal Forms6. Top Down Parsing7. Bottom Up Parsing8. Languages that Are and Are Not Context FreeD. Recursively Enumerable Languages, Turing Machines, and Decidability1. Turing Machines2. Computing with Turing Machines3. Recursively Enumerable and Recursive Languages4. Turing Machine Extensions5. Problem Encoding, Turing Machine Encoding, and the Universal Turing Machine6. Grammars and Turing Machines7. Undecidability8. Introduction to Complexity TheoryII. HomeworkA. Review1. Basic TechniquesB. Regular Languages and Finite State Machines1. Strings and Languages2. Languages and Regular Expressions3. Deterministic Finite Automata4. Regular Expressions in UNIX5. Nondeterministic Finite Automata6. Review of Equivalence Relations7. Finite Automata, Regular Expressions, and Regular Grammars8. Languages that Are and Are Not Regular9. State MinimizationC. Context-Free Languages and Pushdown Automata1. Context Free Grammars2. Parse Trees3. Pushdown Automata4. Pushdown Automata and Context-Free Grammars5. Parsing6. Languages that Are and Are Not Context-FreeD. Recursively Enumerable Languages, Turing Machines, and Decidability1. Turing Machines2. Computing with Turing Machines3. Turing Machine Extensions4. Unrestricted Grammars5. UndecidabilityE. Review1. ReviewIII. Supplementary MaterialsIV. The Three Hour Tour through Automata TheoryV. Review of Mathematical ConceptsVI. Regular Languages and Finite State MachinesVII. Context-Free Languages and Pushdown AutomataVIII. Recursively Enumerable Languages, Turing Machines, and DecidabilityCS 341Dr. BakerFall 200?For late-breaking information and news related to the class, seehttp://www.cs.utexas.edu/users/dbaker/cs341/Acknowledgements:This material was assembled by Elaine Rich, who allowed me to use it wholesale. I am greatly indebted to her for her efforts.Table of ContentsI. Lecture NotesA. Overview and Introduction1. The Three Hour Tour Through Automata Theory2. What is a Language?B. Regular Languages and Finite State Machines1. Regular Languages2. Finite State Machines3. Nondeterministic Finite State Machines4. Interpreters for Finite State Machines5. Equivalence of Regular Languages and FSMs6. Languages that Are and Are Not Regular7. A Review of Equivalence Relations8. State Minimization9. Summary of Regular Languages and Finite State MachinesC. Context-Free Languages and Pushdown Automata1. Context Free Grammars2. Parse Trees3. Pushdown Automata4. Pushdown Automata and Context-Free Languages5. Grammars and Normal Forms6. Top Down Parsing7. Bottom Up Parsing8. Languages that Are and Are Not Context FreeD. Recursively Enumerable Languages, Turing Machines, and Decidability1. Turing Machines2. Computing with Turing Machines3. Recursively Enumerable and Recursive Languages4. Turing Machine Extensions5. Problem Encoding, Turing Machine Encoding, and the Universal Turing Machine6. Grammars and Turing Machines7. Undecidability8. Introduction to Complexity TheoryII. HomeworkA. Review1. Basic TechniquesB. Regular Languages and Finite State Machines1. Strings and Languages2. Languages and Regular Expressions3. Deterministic Finite Automata4. Regular Expressions in UNIX5. Nondeterministic Finite Automata6. Review of Equivalence Relations7. Finite Automata, Regular Expressions, and Regular Grammars8. Languages that Are and Are Not Regular9. State MinimizationC. Context-Free Languages and Pushdown Automata1. Context Free Grammars2. Parse Trees3. Pushdown Automata4. Pushdown Automata and Context-Free Grammars5. Parsing6. Languages that Are and Are Not Context-FreeD. Recursively Enumerable Languages, Turing Machines, and Decidability1. Turing Machines2. Computing with Turing Machines3. Turing Machine Extensions4. Unrestricted Grammars5. UndecidabilityE. Review1. ReviewIII.Supplementary MaterialsIV. The Three Hour Tour through Automata TheoryV. Review of Mathematical ConceptsVI. Regular Languages and Finite State MachinesVII. Context-Free Languages and Pushdown AutomataVIII. Recursively Enumerable Languages, Turing Machines, and
View Full Document
Unlocking...