## CS6503 TOC Syllabus

Anna University Regulation 2013 CSE **CS6503 TOC Important Questions** for all 5 units are provided below. Download link for **CSE 5th SEM CS6503 Theory of Computation Answer Key** is listed down for students to make perfect utilization and score maximum marks with our study materials.

### Anna University Regulation 2013 Computer Science & Engineering (CSE) 5th SEM CS6503 TOC-Theory of Computation Syllabus

**CS6503 THEORY OF COMPUTATION L T P C 3 0 0 3**

#### UNIT I

Understand various Computing models like Finite State Machine, Pushdown Automata, and Turing Machine.

Be aware of Decidability and Un-decidability of various problems.

Learn types of grammars.

FINITE AUTOMATA 9

Be aware of Decidability and Un-decidability of various problems.

Learn types of grammars.

FINITE AUTOMATA 9

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 9

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 9

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 II GRAMMARS 9

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 9

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

55

UNIT IV TURING MACHINES 9

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 9

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.

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 9

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.

OUTCOMES:

At the end of the course, the student should be able to:

At the end of the course, the student should be able to:

- Design Finite State Machine, Pushdown Automata, and Turing Machine.
- Explain the Decidability or Undecidability of various problemsTEXT BOOKS:

1. Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata Theory, Languages and Computations”, Second Edition, Pearson Education, 2008. (UNIT 1,2,3)

2. John C Martin, “Introduction to Languages and the Theory of Computation”, Third Edition, Tata McGraw Hill Publishing Company, New Delhi, 2007. (UNIT 4,5)

REFERENCES:

2. John C Martin, “Introduction to Languages and the Theory of Computation”, Third Edition, Tata McGraw Hill Publishing Company, New Delhi, 2007. (UNIT 4,5)

REFERENCES:

- Mishra K L P and Chandrasekaran N, “Theory of Computer Science – Automata, Languages and Computation”, Third Edition, Prentice Hall of India, 2004.
- Harry R Lewis and Christos H Papadimitriou, “Elements of the Theory of Computation”, Second Edition, Prentice Hall of India, Pearson Education, New Delhi, 2003.
- Peter Linz, “An Introduction to Formal Language and Automata”, Third Edition, Narosa Publishers, New Delhi, 2002.
- Kamala Krithivasan and Rama. R, “Introduction to Formal Languages, Automata Theory and Computation”, Pearson Education 2009

If you require any other notes/study materials, you can comment in the below section.

__Related Links__

__Related Links__

**For CS6503 TOC Previous Year Question Papers – Click here**

**For CS6503 TOC Question Bank/2marks 16marks with answers –**

__Click here__**For CS6503 TOC Important Questions/Answer Key –**

__Click here__**For CS6503 TOC Lecture Notes –**

__Click here____Search Terms__

__Search Terms__

Anna University 5th SEM CSE TOC Syllabus

CS6503 Theory of Computation Syllabus free download

Anna University CSE TOC Syllabus Regulation 2013

CS6503 Syllabus, TOC Unit wise Syllabus – CSE 5th Semester