**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.

**UNIT V UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS CS6503 Theory of Computation Syllabus**

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**