CS6503 Theory of Computation Syllabus Notes Question Papers 2 Marks with Answers Question Bank with answers Anna University CS6503 TOC Notes Syllabus 2 Marks with answers Part A Part B Problems Anna University CSE 5th Semester & IT 8th Semester Common to all Departments - Regulation 2013 5th & 8th Semester Syllabus Notes

Anna University CS6503 Theory of Computation Notes Syllabus 2 marks with answers Part A Question Bank with answers

Anna University CS6503 Theory of Computation Syllabus Notes 2 marks with answer is provided below. CS6503 Notes Syllabus all 5 units notes are uploaded here. CS6503 TOC Syllabus notes download link is provided and students can download the CS6503 Syllabus and Lecture Notes and can make use of it.

CS6503 THEORY OF COMPUTATION  SYLLABUS REGULATION 2013
UNIT I FINITE AUTOMATA
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.

Other Subjects related to CSE 5th Semester

CSE Regulation 2008 2nd 4th 6th 8th Semester Notes - Click here
CSE Regulation 2008 1st 3rd 5th 7th Semester Notes - Click here

CHECK ALSO
Anna University Regulation 2013 UG Syllabus - Click here