CS2303 THEORY OF COMPUTATION syllabus

CS2303                   THEORY OF COMPUTATION                                                L T P C           
                                                                                                                                      3 1 0 4

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
TEXT BOOK:
1.  J.E.  Hopcroft,  R.  Motwani  and  J.D.  Ullman,  “Introduction  to  Automata  Theory,
Languages and Computations”, second Edition, Pearson Education, 2007.

REFERENCES:
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, 1998.
4.   Micheal Sipser, “Introduction of the Theory and Computation”, Thomson Brokecole,
1997.
5.  J.  Martin,  “Introduction  to  Languages  and  the  Theory  of  computation”        
Third Edition,  Tata Mc Graw Hill, 2007