CS2303 THEORY OF COMPUTATION SYLLABUS | ANNA UNIVERSITY BTECH IT 7TH SEMESTER SYLLABUS REGULATION 2008 2011-2012 BELOW IS THE ANNA UNIVERSITY SEVENTH SEMESTER B.TECH. INFORMATION TECHNOLOGY DEPARTMENT SYLLABUS IT IS APPLICABLE FOR ALL STUDENTS ADMITTED IN THE YEAR 2011-2012 (ANNA UNIVERSITY CHENNAI,TRICHY,MADURAI,TIRUNELVELI,COIMBATORE), 2008 REGULATION OF ANNA UNIVERSITY CHENNAI AND STUDENTS ADMITTED IN ANNA UNIVERSITY CHENNAI DURING 2009
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.
TOTAL : 45 PERIODS
72
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, 200UNIT III
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”, 3rd
Edition,Tata Mc Graw Hill, 2007
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.
TOTAL : 45 PERIODS
72
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, 200UNIT III
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”, 3rd
Edition,Tata Mc Graw Hill, 2007
No comments:
Post a Comment
Any doubt ??? Just throw it Here...