Quick Links

University Papers | University Syllabus | Entrance Exam |

PSU Papers | Bank Papers | Placement Papers |

VTU | Anna Univerity Syllabus | Anna Univerity Papers |

**Anna University**

**Question Paper Code : 20368**

**B.E/B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2018.**

**Fifth**

**Semester**

**Computer Science and Engineering**

**CS 6503 Theory of Computation**

**( Common to**

**Information Technology )**

**( Regulation 2013 )**

**Download PDF**

**For More 1st Year Question Papers**

**For More Question paper of CSE**

**For More Question paper of IT**

**Books:**

Anna university all semester examination books and study material can be accessed through below link. Feel free search for different subject books and authors. The link will provide both local and foreign author books for references. Share the page with friends and college students as required.

**GATE:**

GATE papers can be a good practice for any competitive technical exams like DRDO, ISRO, REC, BEL, BHEL, GAIL, ONGC, IOC, NTPC, NHPC etc. As candidates we can prepare for GATE exams and try solving the papers for getting good score in other entrance examinations.

CS6503 Theory of Computation Syllabus

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.

OUTCOMES:

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 problems

TEXT 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:

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

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.

OUTCOMES:

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 problems

TEXT 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:

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

## 0 Comments