CS 341 Dr. Baker Fall 200? For late-breaking information and news related to the class, see http://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 Contents I. Lecture Notes A. Overview and Introduction 1. The Three Hour Tour Through Automata Theory 2. What is a Language? B. Regular Languages and Finite State Machines 3. Regular Languages 4. Finite State Machines 5. Nondeterministic Finite State Machines 6. Interpreters for Finite State Machines 7. Equivalence of Regular Languages and FSMs 8. Languages that Are and Are Not Regular 9. A Review of Equivalence Relations 10. State Minimization 11. Summary of Regular Languages and Finite State Machines C. Context-Free Languages and Pushdown Automata 12. Context Free Grammars 13. Parse Trees 14. Pushdown Automata 15. Pushdown Automata and Context-Free Languages 16. Grammars and Normal Forms 17. Top Down Parsing 18. Bottom Up Parsing 19. Languages that Are and Are Not Context Free D. Recursively Enumerable Languages, Turing Machines, and Decidability 20. Turing Machines 21. Computing with Turing Machines 22. Recursively Enumerable and Recursive Languages 23. Turing Machine Extensions 24. Problem Encoding, Turing Machine Encoding, and the Universal Turing Machine 25. Grammars and Turing Machines 26. Undecidability 27. Introduction to Complexity TheoryII. Homework A. Review 1. Basic Techniques B. Regular Languages and Finite State Machines 2. Strings and Languages 3. Languages and Regular Expressions 4. Deterministic Finite Automata 5. Regular Expressions in UNIX 6. Nondeterministic Finite Automata 7. Review of Equivalence Relations 8. Finite Automata, Regular Expressions, and Regular Grammars 9. Languages that Are and Are Not Regular 10. State Minimization C. Context-Free Languages and Pushdown Automata 11. Context Free Grammars 12. Parse Trees 13. Pushdown Automata 14. Pushdown Automata and Context-Free Grammars 15. Parsing 16. Languages that Are and Are Not Context-Free D. Recursively Enumerable Languages, Turing Machines, and Decidability 17. Turing Machines 18. Computing with Turing Machines 19. Turing Machine Extensions 20. Unrestricted Grammars 21. Undecidability E. Review 22. Review III. Supplementary Materials § The Three Hour Tour through Automata Theory § Review of Mathematical Concepts § Regular Languages and Finite State Machines § Context-Free Languages and Pushdown Automata § Recursively Enumerable Languages, Turing Machines, and
View Full Document
Unlocking...