IT 312 Theory of Computation

Covers the foundations of automata theory, computability theory, and complexity theory. Shows relationship between automata and formal languages. Addresses the issue of which problems can be solved by computational means (decidability vs undecidability), and Introduces concepts related to computational complexity of problems. Discusses formal languages and automata, regular expressions, pumping lemma, context-free languages, parsing, Turing machines and complexity classes. Students must achieve a minimum grade of C. Prerequisite: IT 112 with a grade of C or higher; and MA 260 with a grade of C or higher. (3)