CS 373: Introduction to Theory of Computation
Fall 2012
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.