Sunday, July 8, 2012

CS9302-THEORY OF COMPUTATION-B.E -CSE-COMPUTER SCIENCE AND ENGINEERING FIFTH-V SEMESTER 2008 REGULATION ANNA UNIVERSITY SYLLABUS



CSE Computer Science And Engineering V-fifth Semester Syllabus 2008 Regulation Anna University


AIM:
To have foundation on automata languages and grammar.

OBJECTIVES:
·    Develop the concepts and skills necessary to be able to evaluate the compatibility and undecidability.

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         UNDECIDABILITY                                                                                      9
A language that is not Recursively Enumerable (RE) An undecidable problem that is RE Undecidable problems about Turing Machine Posts Correspondence Problem – The classes P and NP.





TEXT BOOK


TOTAL: 45 PERIODS


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.R.  Lewis  and  C.H.  Papadimitriou,  Elements  of  the  theory  of  Computation, Second Edition, Pearson Education, 2003.
2.  J. Martin, Introduction to Languages and the Theory of Computation, Third Edition, Tata Mc Graw Hill, 2003.
3.  Micheal Sipser, Introduction of the Theory and Computation, Thomson Brokecole,
1997.

7/08/2012 01:13:00 AM

0 comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...