Apr 27, 2024  
2020-2021 UMaine Undergraduate Catalog 
    
Catalog Navigation
  Catalog Home
  President’s Message
  Abbreviations
  Academic Calendar
  Academic Standing
  Admission
  Auxiliary Services
  Colleges and Programs
  Course Descriptions
  Degree / Graduation Requirements
  Disclaimers
  Enrollment Status
  Expenses and Fees
  Facilities and Centers
  Financial Aid
  Grades and Grading
  Graduate Catalog
  Honors College
  Majors and Minors
  Official Records
  Officers and Faculty
  Seal of Biliteracy Credit Table
  Student Services and Facilities
  Test Credit Tables
  Transfer Credit
  University Overview
  University Wide Academic Programs
HELP
2020-2021 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.

Prerequisites: COS 301

Course Typically Offered: Spring

Credits: 3