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