CS2303 THEORY OF COMPUTATION Question Paper / Question Bank Nov / Dec - 2012

CS2303 THEORY OF COMPUTATION  Question papers Previous Year

Subject Name: Theory Of Computation

Subject Code : CS2303

Regulation : 2008

University : Anna University

Semester : Fifth

Type: CS2303 TOC Question paper / Question Bank

Year: Nov / Dec - 2012

Download CS2303 THEORY OF COMPUTATION Question Paper / Question Bank Nov / Dec - 2012

CS2303 THEORY OF COMPUTATION Syllabus

UNIT I AUTOMATA  9
Introduction to formal proof – Additional forms of proof – Inductive proofs –Finite
Automata (FA) – Deterministic Finite Automata (DFA) – Non-deterministic Finite
Automata (NFA) – Finite Automata with Epsilon transitions.

UNIT II REGULAR EXPRESSIONS AND LANGUAGES 9
Regular Expression – FA and Regular Expressions – Proving languages not to be
regular – Closure properties of regular languages – Equivalence and minimization of
Automata.

UNIT III CONTEXT-FREE GRAMMARS AND LANGUAGES 9
Context-Free Grammar (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.
46

UNIT IV PROPERTIES OF CONTEXT-FREE LANGUAGES 9
Normal forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing
Machines – Programming Techniques for TM.

UNIT V UNDECIDABALITY 9
A language that is not Recursively Enumerable (RE) – An undecidable problem that is
RE – Undecidable problems about Turing Machine – Post’s Correspondence Problem –
The classes P and NP.

Tweet