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.

News and Reminders:

• Please read the newsgroup for timely announcements.
• Class newsgroup: Local group umaine.cos451 on NNTP server news.cs.umaine.edu. Web interface to get started: http://cs.umaine.edu/~chaw/news/.
• The most recent version of this document may be found at http://cs.umaine.edu/~chaw/cos451/.
• Some sections below point to material in separate documents that are found on the class Web site, linked from the online version of this document.
• Please use the PDF version of this document for printing and reference: cos451.pdf

© 2013 Sudarshan S. Chawathe