#1
26th July 2016, 02:52 PM
| |||
| |||
RGPV TOC Syllabus
I want the syllabus of Theory of Computation ( TOC ) of B.E. Computer Science and Engineering of Rajiv Gandhi Proudyogiki Vishwavidyalaya?
|
#2
26th July 2016, 03:26 PM
| |||
| |||
Re: RGPV TOC Syllabus
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 |