CS6503 Theory of Computation 

CS6503 Theory of Computation | Important  Questions | Question bank | Syllabus | Model and Previous Question papers | Download PDF Exammain.com Important Questions is available for download in this page for CS6503 Theory of ComputationCS6503 Theory of Computation. Students can download the Important Questions in the PDF format or in Word format. Questions Bank and Previous year question papers also be available in this page  . Important Questions provided here are the Expected questions that are possible to be appeared in the upcoming exams. you can make use of the below questions and prepare for your exams. CS6503 Theory of Computation Important Questions . Download the Important Questions using the below link.

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
Syllabus	Click Here to Download
Part A Important Questions	Click Here to Download
Part B Important Questions	Click Here to Download  >>
Question Bank	Click Here to Download
Full Study Material	Click Here to Download
Other Subject Important Questions	Click Here to Download

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 :

CS6503 Theory of Computation Notes – Click here to Download 

CS6503 Theory of Computation Questions Papers – Click here to Download 

CS6503 Theory of Computation 2 marks with answers – Click here to Download 

Check Anna University –  Exam Result | Internal Mark    >>

Check Anna University Syllabus All Department – Click Here to Download  >>  

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 exammain@gmail.com We will mention your name here.