UG syllabus R 2013

CS6503 Syllabus Theory of Computation Regulation 2013 Anna University

CS6503 Syllabus Theory of Computation

CS6503 Syllabus Theory of Computation Regulation 2013 Anna University free download. Theory of Computation TOC CS6503 Syllabus pdf free download.

UNIT I FINITE AUTOMATA CS6503 Syllabus Theory of Computation

Introduction- Basic Mathematical Notation and techniques- Finite State systems – Basic Definitions – Finite Automaton – DFA & NDFA – Finite Automaton with €- moves – Regular Languages- Regular Expression – Equivalence of NFA and DFA – Equivalence of NDFA‟s with and without €-moves – Equivalence of finite Automaton and regular expressions –Minimization of DFA- – Pumping Lemma for Regular sets – Problems based on Pumping Lemma.

UNIT II GRAMMARS CS6503 Syllabus Theory of Computation TOC

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 CS6503 Syllabus Theory of Computation

Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Equivalence of Pushdown automata and CFL – pumping lemma for CFL – problems based on pumping Lemma.

UNIT IV TURING MACHINES CS6503 Syllabus Theory of Computation TOC

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.


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.

Subject Name Theory of Computation
Subject code CS6503
Regulation 2013

CS6503 Syllabus Theory of Computation click here to download 

CS6503 Notes Theory of Computation

CS6503 Important Questions Theory of Computation

CS6503 Question Bank Theory of Computation


Leave a Reply

Your email address will not be published. Required fields are marked *