Introduction

Formal language theory, Formal proof, Inductive proofs and Central concepts of automata theory.

Finite Automata

Deterministic finite automata, Nondeterministic finite automata, Finite automata with ε-transitions, Equivalence and conversion of deterministic and nondeterministic finite automata.

Regular Expressions and Languages

Regular expressions, Algebraic laws for regular expressions, Regular languages, Pumping lemma, Closure and Decision properties of regular languages.

Context Free Grammar and Languages

Context free grammars, Parsing (or derivation) and parse trees, Ambiguity in grammars and languages, Normal forms for context-free grammars, Pumping lemma for CFL’s, Closure and Decision properties of CFL’s.

Push Down Automata

Push down automata, Acceptance by empty store and final state, Equivalence between pushdown automata and context-free grammars, Deterministic push down automata.

Turing Machines

Turing machines, The church-Turing machine, Techniques for Turing machine construction, Configurations, Computing with Turing machines, Restricted Turing machines, Turing machines and computers, Combining Turing machines.

Undecidability

Recursively enumerable language, The undecidability of the halting problem, Undecidable problems about Turing machines, Post’s correspondence problem.

Complexity Theory

The classes P, NP, examples of problems in these classes. P versus NP question. NP completeness, Polynomial time reducibility, The Cook-Levin theorem.

Examples of NP complete problems

Vertex cover problem, Hamiltonian path problem. Approximation algorithm, Probabilistic algorithms.