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.

Prerequisites: CS 1073, CS 1303, and 30ch.