Dec 09, 2023  
2022-2023 UMaine Undergraduate Catalog 
2022-2023 UMaine Undergraduate Catalog [ARCHIVED CATALOG]

COS 451 - Automata, Computability, and Languages

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

General Education Requirements:

Prerequisites: Grade of C- or higher COS 301

Course Typically Offered: Spring

Credits: 3