Theory of Computation

Syllabus

1. Introduction
   1. Set, relation, function, Proof techniques.
   2. Alphabets, language, regular expression.
2. Finite Automata
   1. Deterministic Finite Automata.
   2. Non-Deterministic Finite Automata.
   3. Equivalence of regular language and finite automata.
   4. Regular language, properties of regular language.
   5. Pumping lemma for regular language.
   6. Decision algorithms for regular languages.
3. Context free language
   1. Context free grammar.
   2. Derivative trees, simplification of context free grammar.
   3. Chomsky normal form.
   4. Push down automata.
   5. Equivalence of context free language and push down automata.
   6. Pumping lemma for context free language.
   7. Properties of context free language.
   8. Decision algorithms for context free language.
4. Turing machine
   1. Definition of Turing machine, notation for Turing machine.
   2. Computing with Turing machine.
   3. Extensions of Turing machine.
   4. Unrestricted grammar.
   5. Recursive function theory.
5. Undecidability
   1. The Church-Turing thesis.
   2. Halting Problem, Universal Turing machine.
   3. Undecidable problems about Turing machines, grammars.
   4. Properties of Recursive, Recursively enumerable languages.
6. Computational Complexity
   1. Class P, Class NP, NP-complete problems.