COS 451: Automata, Computability, and Languages

Sudarshan S. Chawathe
University of Maine

Spring 2013

Fundamentals of formal languages and the mathematical theory of computation; finite-state automata, nondeterminism, regular expressions, and Kleenes Theorem; context-free grammars, pushdown automata, the correspondence theorem and the pumping lemma; computability, Turing machines, and the halting problem.

Prerequisite: COS 250.

Contact Information
Online Resources
Grading Scheme
Textbook and Readings
Exercises, Homeworks, Tests, and Notes

News and Reminders: