SEMESTER V CS1303 – THEORY OF COMPUTATION ANNA UNIVERSITY TIRUCHIRAPPALLI Tiruchirappalli - 620 024

SEMESTER V CS1303  –  THEORY OF COMPUTATION

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 GRAMMAR 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   UNDECIDABILITY                                             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.

  Total: 45
TEXT BOOK
1.  J.E. Hopcroft, R. Motwani and J.D Ullman, “Introduction to Automata Theory, Languages and
Computations”, Second Edition, Pearson Education,  2003.

REFERENCES
1.  H. Lewis and C.H Papadimitriou, “Elements of the Theory of Computation”, Second Edition,
Pearson Education/PHI, 2003.
2.  J. Martin, “Introduction to Languages and the Theory of Computation”, Third Edition, TMH,
2003.
3.  Micheal Sipser, “Introduction of the Theory and Computation”, Thomson Brokecole, 1997.

FEEL USEFUL PLEASE GIVE +1