CMSCI 485 - Theory of Computation

Credits: (3)
This is an investigation into the theoretical basis of computation. Topics include a study of finite state automata, regular expressions, context-free grammars, pushdown automata, the pumping lemma, Turing machines, undecidability and intractable problems. Prerequisite(s): CMSCI 254 Data Structures and Algorithms (3) and MATH 228 Discrete Mathematics (3) or permission of the instructor. (Spring of Even years)