CS6503 Theory of Computation Syllabus Notes Question Papers Question Bank with answers download
Download Question bank, Question papers, Notes, Syllabus for CS6503 Theory of Computation (TOC) regulation 2013 in PDF
CS6503 Theory of Computation Syllabus - TOC Syllabus
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
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
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
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
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.
CS6503 Theory of Computation (TOC) - All useful study materials
|CS6503 Study Materials||Download Link|
|CS6503 Syllabus||Click here to download Syllabus|
|CS6503 Notes||Notes 1 Link | Notes 2 Link | Notes 3 Link|
|CS6503 Question Bank||QB 1 Link | QB 2 Link | QB 3 Link|
|CS6503 Question Papers||Click here to download Question paper|
|CS6503 2 marks with Answers (Part A)||Click here to download 2 marks with answers|
CS6503 Anna University
CS6503 Theory of Computation syllabus pdf
CS6503 Theory of Computation notes prepared by lectures
CS6503 Theory of Computation regulation 2013
CS6503 Theory of Computation question bank
CS6503 Theory of Computation question papers
CS6503 Theory of Computation important questions
CS6503 Theory of Computation ebook