Translate

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
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)

2 Responses so far.

  1. Anonymous says:

    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?

  2. Anonymous says:

    i need new semester 5 all subject notes..plz....:{
    clothiersain@gmail.com

Leave a Reply