Computer Science Comprehensive Exam
Automata Syllabus
1997-1998
Topics:
Regular Languages
- Finite Automata
- Regular Expressions and Sets
- Closure Properties
- Pumping Lemma
- Myhill-Nerode Theorem and Minimizing DFAs
- Decision Algorithms
Context-Free Language
- Context-Free Grammars
- Push-down Automata
- Normal Forms for Grammars
- Closure Properties
- Decision Algorithms
- Pumping Lemma, Ogden's Lemma
Turing Machines
- Turing Machine Specifications
- Recursive and Recursively Enumerable Languages
- Universal Machines
- Undecidable Languages and Problems
- Rice's Theorem
Complexity
- Polynomial time and space
- Complete problems
- Intractability
Reference:
- Hopcroft, J., and Ullman, J., Introduction to Automata Theory,
Languages and Computation, Addison-Wesley, 1979, Chapters 2-8, 13.1-13.6
(except material on NP-completeness).
![[PREV]](../../Images/larrw.gif)
![[UP]](../../Images/uarrw.gif)
![[CSGSA]](../../Images/CSGSA-button.gif)
![[NEXT]](../../Images/rarrw.gif)