Module 1

Introduction to the theory of computation – Set theory – Definition of sets – Properties – Countability – Uncountability – Equinumerous sets – Functions – Primitive recursive and partial recursive functions – Computable and non computable functions – Diagonalization principle – Formal representation of languages – Chomsky Classification. 

Module 2

Introduction to Automata theory – Definition of Automation – Finite Automata – Formal definition – Language acceptability by Finite Automata – Transition Diagrams and Transition systems – Deterministic and Nondeterministic finite automation – Finite Automation with -Transitions – Eliminating -Transitions – Conversion of NFA to DFA – Regular operations – Regular Expressions – Pumping lemma for regular languages – Applications of finite state automata – Lexical analysers – Text search. 

Module 3

Pushdown Automata – Formal definition – Language acceptability by PDA – Deterministic and nondeterministic PDA – Context free grammar – Applications of PDA – Parsing. 

Module 4

Turing Machines – Formal definition – Language acceptability – Universal Turing Machines – Halting Problem of Turing Machines – Church’s Thesis – Godelization. 

Module 5

Algorithmic complexity – Tractable and intractable problems – Complexity classes – Class P – Class NP – NP Complete and NP Hard problems. 

References

1. Introduction to the Theory of Computation- Michael Sipser, Brooks/Cole (Thomson Learning)
2. Theory of Computer Science – K.L.P. Mishra, N. Chandrashekharan, Prentice Hall of India
3. Elements of the theory of computation -Harry R Lewis, Christos H Papadimitriou Prentice Hall of India / Pearson Education Asia
4. The Theory of Computation – Bernard M Morct (Pearson Edn)
5. Introduction to Automata Theory, Languages & Computation John Hopcroft, Rajeev Motwani & Jeffry Ullman (Pearson Edn)