CS6503 TOC Syllabus
Anna University Regulation 2013 CSE CS6503 TOC Important Questions for all 5 units are provided below. Download link for CSE 5th SEM CS6503 Theory of Computation Answer Key is listed down for students to make perfect utilization and score maximum marks with our study materials.
Anna University Regulation 2013 Computer Science & Engineering (CSE) 5th SEM CS6503 TOC-Theory of Computation Syllabus
CS6503 THEORY OF COMPUTATION L T P C 3 0 0 3
Be aware of Decidability and Un-decidability of various problems.
Learn types of grammars.
FINITE AUTOMATA 9
UNIT II GRAMMARS 9
Grammar Introduction– Types of Grammar – Context Free Grammars and Languages– Derivations and Languages – Ambiguity- Relationship between derivation and derivation trees – Simplification of CFG – Elimination of Useless symbols – Unit productions – Null productions – Greiback Normal form – Chomsky normal form – Problems related to CNF and GNF.
UNIT III PUSHDOWN AUTOMATA 9
Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Equivalence of Pushdown automata and CFL – pumping lemma for CFL – problems based on pumping Lemma.
Definitions of Turing machines – Models – Computable languages and functions –Techniques for Turing machine construction – Multi head and Multi tape Turing Machines – The Halting problem – Partial Solvability – Problems about Turing machine- Chomskian hierarchy of languages.
UNIT V UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS 9
Unsolvable Problems and Computable Functions – Primitive recursive functions – Recursive and recursively enumerable languages – Universal Turing machine. MEASURING AND CLASSIFYING COMPLEXITY: Tractable and Intractable problems- Tractable and possibly intractable problems – P and NP completeness – Polynomial time reductions.
At the end of the course, the student should be able to:
- Design Finite State Machine, Pushdown Automata, and Turing Machine.
- Explain the Decidability or Undecidability of various problemsTEXT BOOKS:
2. John C Martin, “Introduction to Languages and the Theory of Computation”, Third Edition, Tata McGraw Hill Publishing Company, New Delhi, 2007. (UNIT 4,5)
- Mishra K L P and Chandrasekaran N, “Theory of Computer Science – Automata, Languages and Computation”, Third Edition, Prentice Hall of India, 2004.
- Harry R Lewis and Christos H Papadimitriou, “Elements of the Theory of Computation”, Second Edition, Prentice Hall of India, Pearson Education, New Delhi, 2003.
- Peter Linz, “An Introduction to Formal Language and Automata”, Third Edition, Narosa Publishers, New Delhi, 2002.
- Kamala Krithivasan and Rama. R, “Introduction to Formal Languages, Automata Theory and Computation”, Pearson Education 2009
For CS6503 TOC Previous Year Question Papers – Click here
For CS6503 TOC Question Bank/2marks 16marks with answers – Click here
For CS6503 TOC Important Questions/Answer Key – Click here
For CS6503 TOC Lecture Notes – Click here
Anna University 5th SEM CSE TOC Syllabus
CS6503 Theory of Computation Syllabus free download
Anna University CSE TOC Syllabus Regulation 2013
CS6503 Syllabus, TOC Unit wise Syllabus – CSE 5th Semester