## Saturday, June 20, 2015

### CS6503 Theory of Computation Syllabus Notes Question Papers 2 Marks with Answers Regulation 2013 Anna University

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

search by students

CS6503 Theory of Computation Anna university 5th semester Regulation 2013 notes
CS6503 Theory of Computation Anna university 8th semester Regulation 2013 notes
Anna University Regulation 2013 5th Semester Notes
Anna University Regulation 2013 8th Semester Notes
Regulation 2013 8th Semester Notes Anna University
Regulation 2013 5th Semester Notes Anna University
CS6503 Theory of Computation Syllabus Notes 4th Semester- common for all Departments
CS6503 Theory of Computation Notes Syllabus Question Papers Question Bank 2 marks with answers
Anna University CS6503 CSE Notes Syllabus Question Papers 2 marks with answers Part B Problems Regulation 2013

1. pls update the notes for cs6503 (theory of computation)

2. pls update the notes for cs6503 (theory of computation)

3. Anonymous2:56 AM

Pls upload cs6503 important questions soon

4. Anonymous3:23 PM

Cs6503 fast plzzzz