RGPV TOC Syllabus

I want the syllabus of Theory of Computation ( TOC ) of B.E. Computer Science and Engineering of Rajiv Gandhi Proudyogiki Vishwavidyalaya?

[pawan]

Ok, here I am providing you the syllabus of Theory of Computation ( TOC ) of B.E. Computer Science and Engineering of Rajiv Gandhi Proudyogiki Vishwavidyalaya

RGPV BE CSE Theory of Computation ( TOC ) syllabus


UNIT 1: Automata:Basic machine, FSM , Transition graph, Transition matrix, Deterministic and non-deterministic FSM’S, Equivalence of DFA and NDFA, Mealy & Moore machines, minimization of finite automata, Two-way finite automata.
Regular Sets and Regular Grammars:Alphabet, words, Operations, Regular sets, Finite automata and regular expression, Myhill- Nerode theorem Pumping lemma and regular sets, Application of pumping lemma, closure properties of regular sets.

UNIT 2:Context –Free Grammars:
Introduction to CFG, Regular Grammars, Derivation trees and Ambiguity, Simplification of Context free grammars, Normal Forms (Chomsky Normal Form and Greibach Normal forms).

UNIT3: Pushdown Automataefinition of PDA, Deterministic Pushdown Automata, PDA corresponding to given CFG, CFG corresponding to a given PDA. Context Free Languages: The pumping lemma for CFL’s, Closure properties of CFL’s, Decision problems involving CFL’s.

UNIT 4: Turing Machines:Introduction, TM model, representation and languages acceptability of TM Design of TM, Universal TM & Other modification, Church’s hypothesis, composite & iterated TM. Turingmachine as enumerators.Properties of recursive & recursively enumerable languages, Universal Turing machine

UNIT 5: Tractable and Untractable Problems: P, NP, NP complete and NP hard problems, examples of these problems like satisfy ability problems, vertex cover problem, Hamiltonian path problem, traveling sales man problem, Partition problem etc.

Suggested Reading:
1. John E. Hopcroft, Jeffery Ullman,”Introduction to Automata theory, Langauges & computation” , Narosa Publishers.
2. K.L.P Mishra & N.Chandrasekaran,“Theory of Computer Science”, PHI Learning
3. Michael Sipsev,“Theory of Computation”,Cenage Learning
4. John C Martin, “Introdution to languages and theory of computation”, McGraw Hill
5. Daniel I.A. Cohen,“Introduction to Computer Theory”,Wiley India.
6. Kohavi,”Switching & Finite Automata Theory”,TMH

Contact-

RGPV
Airport Bypass Road, Gandhi Nagar
Abbas Nagar, Gandhinagar
Bhopal, Madhya Pradesh 462036