Contents

## 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 __

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

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

Free Download Anna University Engineering Study Materials

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