Categories

# CS8501 Syllabus THEORY OF COMPUTATION Regulation 2017 Anna University

## CS8501 Syllabus THEORY OF COMPUTATION

CS8501 Syllabus Theory Of Computation Regulation 2017 Anna University free download. Theory Of Computation Syllabus CS8501 pdf free download.

### UNIT I AUTOMATA FUNDAMENTALS CS8501 Syllabus THEORY OF COMPUTATION

Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata – Deterministic Finite Automata – Non-deterministic Finite Automata – Finite Automata with Epsilon Transitions

### UNIT II REGULAR EXPRESSIONS AND LANGUAGES CS8501 Syllabus

Regular Expressions – FA and Regular Expressions – Proving Languages not to be regular – Closure Properties of Regular Languages – Equivalence and Minimization of Automata.

### UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES CS8501 Syllabus THEORY OF COMPUTATION

CFG – Parse Trees – Ambiguity in Grammars and Languages – Definition of the Pushdown Automata – Languages of a Pushdown Automata – Equivalence of Pushdown Automata and CFG, Deterministic Pushdown Automata.

### UNIT IV PROPERTIES OF CONTEXT FREE LANGUAGES CS8501 Syllabus THEORY OF COMPUTATION

Normal Forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines – Programming Techniques for TM.

### UNIT V UNDECIDABILITY CS8501 Syllabus THEORY OF COMPUTATION

Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Post‘s Correspondence Problem, The Class P and NP.

OBJECTIVES:

 To understand the language hierarchy
 To construct automata for any given pattern and find its equivalent regular expressions
 To design a context free grammar for any given language
 To understand Turing machines and their capability
 To understand undecidable problems and NP class problems

 Subject name THEORY OF COMPUTATION Short Name TOC Semester 5 Subject Code CS8501 Regulation 2017 regulation

CS8501 Syllabus THEORY OF COMPUTATION Click Here To Download

CS8501 THEORY OF COMPUTATION Notes

CS8501 THEORY OF COMPUTATION Important Questions

CS8501 THEORY OF COMPUTATION Question Bank

CS8501 THEORY OF COMPUTATION Question Paper