Formal Languages, Automata, and Computability

The course title has historical reasons, FLAC might be better called: A Tour of the Computational Universe. We discuss classical results in abstract computability as well as resource bounded computation, in particular finite state machines and their associated algorithmic problems. We will also explore the Chomsky hierarchy and introduce standard complexity classes such as NP and PSPACE. Time permitting, we may take a look some non-traditional models of computation such as cellular automata or infinite time Turing machines.

Needless to say, a solid background in discrete math is necessary for this course. In particular facility will all 15-251 material will be assumed.