See CMPSC 3000 Formal Languages and Automata.
CMPSC 3000 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 3000 Formal Languages and Automata.
Prerequisite(s): Grade of "C" or better in either CMPSC 1500 Program Design or MATH 2200 Introduction to Higher Mathematics and junior standing.