CS 373: Introduction to Theory of Computation

Fall 2013

Course Topics

This course will focus on fundamental mathematical models of computation. We will be interested in both the inherent capabilities and limitations of these computational models as well as their relationships with formal languages. Rigorous arguments and proofs of correctness will be emphasized. Particular topics to be covered include:

• Finite automata, regular languages, and regular grammars.
• Deterministic and nondeterministic computations on various automata.
• Context free grammars, languages, and pushdown-automata
• Turing machines, Church's thesis, and undecidable problems

Prerequisites

The prerequisites for this course are CS 125 (or ECE 190), CS 173 (or MATH 213), and CS 225.

To test the mathematical side of your background, skim through Chapter 0 of the Sipser textbook. You can view Chapter 0 for free on Amazon. You might not be able to produce all the details from memory, but almost all of it should look like something you used to know.

Other experience (e.g. advanced math courses) may be able to serve in lieu of these prerequisites, especially CS 225. If you aren't sure of your background, please speak to the instructor.