Computer Science2333Computability and Formal LanguagesCS4 ch (3C 1T)

This course introduces students to some of the fundamental ideas in theoretical computer science: functions and relations, formal languages, finite automata, regular languages, context-free grammars, context-free languages, push-down automata, pumping lemmas, Turing machines, the Church-Turing thesis, recursive and recursively enumerable languages, the Chomsky hierarchy, the halting problem and other unsolvable decision problems, problem reducibility, and fundamental computational complexity classes. Note: Credit is not given for both CS 2333 and CS 2303.

Prerequisites: CS 1303, 30 ch and (CS 1073 or CS 1003).