UG syllabus R-2017

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

Leave a Reply

Your email address will not be published. Required fields are marked *