Course Catalogs

You are viewing the
2012-2013 Course Catalog

CMPSC 200 Formal Languages and Automata

3 hours


An overview of formal models of computation and complexity classes. Topics include formal languages (finite automata, regular expressions, push-down automata, context-free grammars, and Turing machines), Church's thesis, computability, non-determinism, and NP-completeness. Same as MATH 200 Formal Languages and Automata.

Prerequisite(s): Grade of "C" or better in either CMPSC 100 Discrete Mathematics or MATH 111 Introduction to Higher Mathematics and junior standing.

(Normally offered alternate years.)