Trees and graphs, Set notations, relations, inductive proofs.

Finite state systems, Non-deterministic finite automata, Regular expressions, Two-way finite automata, Applications of finite automata, Properties of Regular Sets: the pumping lemma, closure properties and decision algorithms, Minimization of finite automata.

Introduction to context-free grammars, Derivation trees, Normal forms: Chomsky and Greibach, Inherently ambiguous context-free languages, Context-Free Languages: the pumping lemma, closure properties and decision algorithms.

Informal description of pushdown automata, pushdown automata and context-free languages.

Introduction to Turing Machines and the Turing machine model, Computable languages and functions, Techniques for Turing machine construction and modifications, Church’s hypothesis, Turing machines as enumerators, Restricted Turing machines equivalent.

Decidable and undecidable problems, Properties of recursive and recursively enumerable languages, Universal Turing machines and an undecidable problem, Rice’s theorem and more undecidable problems, Undecidability of Post’s correspondence problem, Greibach’s theorem, Introduction to recursive function theory, Oracle computations.

Linear speed-up, tape compression, and reductions in the number of tapes, Hierarchy theorems, Relations among complexity measures, Translational lemmas and nondeterministic hierarchies, Properties of general complexity measures, Axiomatic complexity theory.

Polynomial time and space, Some NP-complete problems, The class co-NP, PSPACE-complete problems, Complete problems for P and NSPACE(log n), The P = NP question for Turing machines with oracles: limits on the ability to tell whether P = NP.

Total