Study of three classical formal models of computation--finite state machines, context-free grammars, and Turing machines--and the corresponding families of formal languages. Power and limitations of each model. Parsing. Non-determinism. The Halting Problem and undecidability. The classes P and NP, and NP-completeness. 3 credit hours.

Grade of C- or better in CSC 226 Discrete Mathematics.

Upon successful completion of this course, a student will be able to...

1. Automata Theory:
1. Develop skill at stating and proving mathematical statements about formal models of computation.
2. Define formal languages and explain how they can be generated by different automata.
3. Synthesize finite and pushdown automata with specific properties.
4. Convert among multiple representations of finite and pushdown automata.
5. Prove particular problems cannot be solved by finite or pushdown automata using the Pumping Lemma or the closure properties of regular and/or context-free languages.
2. Computability Theory:
1. Define Turing machines and their variants as models of computation.
2. Define computable problems in terms of Turing machines.
3. Use the relationship between recognizability and decidability to determine decidability properties of problems.
4. Prove undecidability using diagonalization and reducibility methods.
3. Computational Complexity Theory:
1. Define, and explain the significance of, the "P = NP?" question and NP-completeness.
2. Define deterministic and nondeterministic computation time and space, and explain the relationships among them.
3. Describe concrete examples of NP-complete problems from different fields.
   

Weekly homework problem sets worth 30% of the grade, two midterm exams worth 20% each, final exam worth 20-25% (to be decided), remainder of grade based on in-class excercises.

Author: Sipser, Title: Introduction to the Theory of Computation, 2nd edition, copyright 2006, Thompson. ISBN: 978-0-534-95097-2