CS2303 THEORY OF COMPUTATION ANNA UNIVERSITY CSE 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.

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.
L: 45, T: 15, TOTAL: 60 PERIODS

Share on Google Plus

About Unknown

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.