COS 451/550: Automata, Computability, andLanguages

Sudarshan S. Chawathe
University of Maine

Spring 2021

This course is an introduction to the theory of computation. Some big questions: What is a computer? How may we model computers and computation? What are the theoretical and practical limits of computation? What do we know about what can, and cannot, and may or may not be computable and efficiently computable? Some more details, from the course catalog: 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.

Prerequisites: COS 301; programming maturity.

COS 550 is the graduate version of this course, which shares most class meetings and coursework with the undergraduate version (COS 454) but that includes additional coursework and is assessed to a higher standard.

Goals and Learning Objectives
 Student Learning Outcomes
Contact Information
Online Resources
Grading Scheme
Textbook and Readings
Exercises, Homeworks, Tests, and Notes
Homework and Project Submissions

News and Reminders: