Thursday, April 21, 2011


CS2303  THEORY OF COMPUTATION                                                

UNIT I                 AUTOMATA                                                                                             
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                                   
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                          
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                           
Normal forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines – Programming Techniques for TM.

UNIT V                  UNDECIDABALITY                                                                               
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.


1.            J.E. Hopcroft, R. Motwani and J.D. Ullman, “Introduction to Automata Theory, Languages and Computations”, second Edition, Pearson Education, 2007.


1.            H.R. Lewis and C.H. Papadimitriou, “Elements of the theory of Computation”, Second Edition, Pearson Education, 2003.
2.            Thomas A. Sudkamp,” An Introduction to the Theory of Computer Science, Languages and Machines”, Third Edition, Pearson Education, 2007.
3.            Raymond Greenlaw an H.James Hoover, “ Fundamentals of Theory of Computation, Principles and Practice”, Morgan Kaufmann Publishers, 1.
4.             Micheal Sipser, “Introduction of the Theory and Computation”, Thomson Brokecole, 17.
5.            J. Martin, “Introduction to Languages and the Theory of  computation”                          Third Edition,  Tata Mc Graw Hill, 2007


Post a Comment