# CS6503 Theory of Computation | Important Questions | Question bank | Syllabus | Model and Previous Question papers | Download PDF

## CS6503 Theory of Computation

Subject Informations :

University        :  Anna University
Department     :  B.E. COMPUTER SCIENCE AND ENGINEERING
Semester          :  05 th sem
Year                  : 03 rd year
Regulation       :  R2013
Subject Code   : CS6503
Subject Name  : Theory of Computation

Are you Searching about Anna University Exams Important Questions ? Exammain.com is the right place to get all semester Anna University Important Questions Download PDF.

CS6503 Theory of Computation | Important  Questions

### CS6503 THEORY OF COMPUTATION – SYLLABUS – R- 2013

OBJECTIVES:

The student should be made to:

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

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.

Also check :

Check Anna University –  Exam Result | Internal Mark    >>

Note : Questions posted in this page should be made use only as a reference material. These Questions may or may not appear in the Semester Examination. Kindly Refer our Questions for preparing for your exams and also share it with your friends.

Mail your study material to [email protected] We will mention your name here.

Most Search Keywords :

CS6503 Theory of Computation  Important Questions
CS6503 Theory of Computation Important Questions
CS6503 Theory of Computation Part B Important Questions
Regulation 2013 CS6503 Theory of Computation Important Questions Part B
Regulation 2013  Important Questions Anna University
CS6503 Theory of Computation Important Questions Anna University
Important Questions Anna University
CS6503 Theory of Computation Important Questions
CS6503 Theory of Computation question bank
CS6503 Theory of Computation Syllabus
CS6503 Theory of Computation Full Study Material
CS6503 Theory of Computation Part B Important Questions
CS6503 Theory of Computation Question Bank
CS6503 Question bank
CS6503 Important Question 2018
CS6503 Theory of Computation Important Questions
CS6503 Important Questions PDF
CS6503 TOC Important Questions
CS6503 Theory of Computation 2 marks with answers
CS6503 QB
CS6503 Theory of Computation Important Questions
CS6503 Theory of Computation Important Questions 2 marks
CS6503 Theory of Computation Important Questions 10 marks