Languages, Machines and Computation

The objective of the course is to introduce students to the foundations of computation.

Objectives

The objective of the course is to introduce students to the foundations of computation. We ask fundamental questions like “What does it mean for a function to be computed?”, “Are all functions computable?”, “Is there a way to measure the hardness of computing a function?” We will see that the above questions are deep, and in the quest for answering them we will learn some fundamental concepts such as state, transition, reduction, decidability.

Important Links

Textbooks and References.

The textbooks for the course are Michael Sipser’s “Introduction to the Theory of Computation” and “Automata and Computability” by Dexter Kozen. The library should have multiple copies. Slides used in last class are here. I also found some very nice slides here.

Syllabus

The topics are broadly categorized as follows.

  • Finite Automata & Regular Languages (Ch 1 of Sipser, Ch 13-16 of Kozen):Introduction to automata theory, languages and computational problems. Finite state automata, Regular Languages. Deterministic and Non-deterministic finite automata, Subset construction. Regular Expressions, Pattern Matching, pumping lemma, DFA state minimization, Myhill Nerode relations, Myhill Nerode theorem.

  • Context Free Languages and Push Down Automata (Ch 2 of Sipser and Ch 20 and 27 of Kozen) :Context free grammars - Derivation trees and ambiguity -Chomsky normal form - Pushdown automata - Acceptance by empty store and final state - Equivalence between push-down automata and context-free grammars - Pumping lemma - PAREN language and its grammar - CYK algorithm - Closure properties of CFL.

  • Turing machines & Computability (Ch 3, 4 and 5 of Sipser): Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Universal Turing machine - Turing recognizable and decidable - linear bounded automata. Decidability; Post’s correspondence problem; Rice’s theorem; decidability of membership, emptiness and equivalence problems of languages, reductions.