Theory of Computation

Revised: January 2006 (David Luginbuhl)

Course Description

An introduction to the theory of computation.  Regular, context-free, and general phrase structure languages along with their associated automata.  Computability in the context of Turing machines, partial recursive functions, and simple programming languages. Complexity theory with an introduction to some of the open classification problems relating to the classes P and NP. This course will require students to read, discover, and clearly write mathematical proofs.  3 credit hours, required for the major. Prerequisite: CS 260.

Text

Required text: Hopcroft, John E., Motwani, Rajeev, and Ullman, Jeffrey D.  Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001.

Grading Procedure

Grading procedures and factors influencing course grade are left to the discretion of individual instructors, subject to general university policy.

Attendance Policy

Attendance policy is left to the discretion of individual instructors, subject to general university policy.

Course Outline

• Mathematical Structures and Proofs.
• Regular Languages and Finite Automata
• Context-Free Languages and Pushdown Automata
• Computability
            o Turing Machines
            o Recursively Enumerable and Recursive Languages
            o Unsolvable Problems
            o Computable Functions