



4. Descriptive Title: Automata and Complexity Theory  
5. Recommended Abbreviation for Transcript (24 characters including
spaces):
Automata and Complexity 

6. Catalog Description (25 words or less):
Computational machine models and their language classes. Undecidability. Resourcebounded computations. Central complexitytheoretic concepts such as complexity classes, reducibility, and completeness. 

7. Basis: L/G ____X_____ P/F ____X______ Audit ____X______  






12. Are you requesting this course satisfy: Humanities ________ Social Science ________ (Must be 1000 or 2000 level)  
13. Probable instructor(s) (Please mark with an asterix any non
tenuretrack individuals):
Yan Ding, Richard Lipton, H. Venkateswaran 

15. Required _____________ Elective _____x______  
16. Please attach a topical outline of the course. 


Course Outline and Syllabus 
INTRODUCTORY CONCEPTS: Formal languages, operations on languages, and basic properties. REGULAR LANGUAGES: Deterministic and nondeterministic finite automata and their equivalence. Closure properties. Pumping lemma. MyhillNerode theorem. CONTEXTFREE LANGUAGES: Contextfree grammars. Ambiguity. Normal forms such as Chomsky Normal Form. Closure properties. Pumping lemms. Pushdown automata. Equivalence of pushdown automata and contextfree grammars. CockeKasamiYounger algorithm. Deterministic contextfree languages. DECIDABILITY: Turing machines. Recursivelyenumerable and recursive languages. Equivalence of varieties of models such as multitape and nondeterministic Turing machines with the deterministic Turing machines. Diagonalization. Undecidability of the Halting problem. REDUCIBILITY: Undecidable problems from Language theory. Post Correspondence Problem. Manyone reducibility. COMPLEXITY THEORY: Time complexity. Complexity classes P and NP. Polynomial time reducibility. NPCompleteness. The CookLevin theorem. Examples of NPComplete problems. Space complexity. Savitch's theorem. PSPACECompleteness. The classes L and NL. NLCompleteness. NL equals CONL. Probabilistic complexity classes. 
Suggested Texts  M. Sipser. Introduction to the theory of Computation, PWS Publishing Company. 