COURSE CONTENTS : CS 5511/ CS505
Theory of Computation
Unit IRGPV 5th Semester, RGPV syllabus, RGTU syllabus, Rgpv 5th sem syllabus, Compiler Design syllabus, cs 5th sem syllabus,RGTU 5th sem syllabus, syllabus
Push – Down Automata: Non deterministic push down automata: Definition of a push down automata, The language accepted by a push down automata, Push down automata and context free languages, Push down automata for context free languages, CFG’s for PDA, Deterministic Push down automata and Deterministic Context free languages, Grammers and Deterministic context free languages
Turning Machines: The Standard Turning Machine: Definition of a Turning Machine, Turning Machines as language accepters, and Turning Machines as Transducers. Combining Turning Machines for complicated tasks, Turning thesis, Other models of Turning Machines.
Limits of algorithmic computation, Some Problems that can not be solved by Turning Machines, Computability and Decidability, the Turning Machine Halting Problem, Reducing one Undecidable Problem to another, Undecidable Problems for Recursively Enumerable languages, The post correspondence problem : Indecidable problems for context free languages, Recursive function, Primitives recursive functions, Ackermanris functions, recursive functions, Post Systems : Rewriting systems : Matrix grammars, Markor Algorithms.