Automata and Formal Languages

The fundamental limitations on mechanized computation. In the first part of the course, the emphasis is on possible versus impossible computations. Three classes of languages are considered: regular, context-free, and recursively enumerable. In the second part of the course the emphasis shifts to possible versus feasible computations.


Semester Offered: