Formal Languages, Automata, and Computability


Some Mealy machines generating a particular transduction monoid.

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.


Klaus Sutner Instructor: Klaus Sutner sutner@cs

Clock Icon
Office hours: Thursday 16:30-18:00, GHC 6015.

TBD TA: Paul Gölz pgoelz@andrew

Clock Icon
Office hours: TBD