See CMPSC 200 Formal Languages and Automata.
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.)