CS505 Theory of Computation ( TOC ) RGTU/RGPV CS 5th sem syllabus

B.E. Computer Science and Engineering VII Semester
CS 5511/ CS505 Theory of Computation

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 Automata:Definition 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

Add to Mixx! Mixx it!
| More


Post a Comment


RGTU Syllabus , RGPV Syllabus © Template Design by Herro | Publisher : Templatemu Copy Protected by RgtuSyllabus.blogspot.com in association with | RollingRoxy.Blogspot.Com | ResultsZone.Blogspot.Com | MBANetBook.Blogspot