CS 475

Finite automata and regular languages; pushdown automata and context-free languages; Turing machines and recursively enumerable sets; linear-bounded automata and context-sensitive languages; computability and the halting problem; undecidable problems; recursive functions; Chomsky hierarchy; computational complexity. Course Information: Same as MATH 475. 3 undergraduate hours. 3 or 4 graduate hours. Prerequisite: CS 374.

Primary Textbook: Theory of Computation by Dexter Kozen

For Background and Additional Topics: Automata and Computability by Dexter Kozen

[1] Recognize regular and non-regular languages (1), (6)

[2] Prove recursive/recursive enumerability of sets (1), (6)

[3] Prove problems to be undecidable/non-recursively enumerable through reductions (6)

[4] Understand the relationship between complexity classes (6)

[5] Prove that a problem belongs to a certain complexity class (1)

[6] Prove that a problem is the hardest in a complexity class through reductions (6)

[7] Understand the power of nondeterminism in a computational setting (6)

[8] Understand the power of randomization in a computational setting (6)

Automata Theory:

• Deterministic/nondeterminstic finite automata
• Regular languages
• 2-way automata, alternation

Recursion Theory:

• Turing machine and its variants
• Recursive enumerability and decidability
• Reductions
• Arithmetic Hierarchy

Complexity Theory

• Definitions of time and space bounded complexity, and classical complexity classes
• Relationship between complexity classes
• Alternation and randomization
• Interactive proofs

2/8/2019by Mahesh Viswanathan