Description:

Introduces the abstract notions of machine computation for honors students. Includes finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Explores what can and cannot be computed by considering various models of computation including Turing machines, recursive functions, and universal machines.

Course Outcome:

• An ability to define and use abstract models of computation such as finite and push-down automata, and analyze their relative expressive power.
• An ability to define, use, and convert between abstract machine models and formal languages.
• An ability to apply abstract models of computation to analyze the power and inherent limitations of algorithms.

Tentative Lesson Plan (Sipser's book):

• Finite automata, non-determinism, regular languages, pumping lemma. [Chap. 0--1](Week 1-4)

• Context-free languages, grammars, pushdown automata [Chap. 2](Week 5-6)

• Turing machines, decidability, reductions, computability [Chap. 3--5](Week 7-12)

• Complexity theory, NP Completeness [Chap. 7](Week 13- 16)