# CS8501 Syllabus THEORY OF COMPUTATION Regulation 2017 Anna University

## CS8501 Syllabus THEORY OF COMPUTATION

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