## Theory of Computation - Computer Science Lecture notes

**Semester 7 - THEORY OF COMPUTATION**

**(S7 -TOC Lecture Notes)**

**Module I to V (1 to 5)**

MG University S7 - Computer Science and Engineering - B.Tech Syllabus

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 1

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.

1. Introduction to the Theory of Computation- Michael Sipser, Brooks/Cole (Thomson Learning)References

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)

It is really a good effort put together really helpful.I have a question in the theory of computation course mod 3 the exercises are given in notes can you provide the solution to the exercises or may be answers to them if possible?

i need new semester 5 all subject notes..plz....:{

clothiersain@gmail.com

hey aaa.... the provided notes is too gud and helpful .. but I cannot download the pdf file ... plzz help me out ..I need to download the file