ANNA UNIVERSITY CHENNAI: CHENNAI – 600 025
B.E DEGREE PROGRAMME COMPUTER SCIENCE AND ENGINEERING
(Offered in Colleges affiliated to Anna University)
CURRICULUM AND SYLLABUS – REGULATIONS – 2004 SEMESTER V
B.E DEGREE PROGRAMME COMPUTER SCIENCE AND ENGINEERING
(Offered in Colleges affiliated to Anna University)
CURRICULUM AND SYLLABUS – REGULATIONS – 2004 SEMESTER V
CS1303 THEORY OF COMPUTATION 3 1 0 100
AIM
To have a introductory knowledge of automata, formal language theory and computability.
To have a introductory knowledge of automata, formal language theory and computability.
OBJECTIVES
• To have an understanding of finite state and pushdown automata.
• To have a knowledge of regular languages and context free languages.
• To know the relation between regular language, context free language and corresponding recognizers.
• To study the Turing machine and classes of problems.
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.
• To have an understanding of finite state and pushdown automata.
• To have a knowledge of regular languages and context free languages.
• To know the relation between regular language, context free language and corresponding recognizers.
• To study the Turing machine and classes of problems.
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.
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.
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.
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.
TUTORIAL 15
TOTAL : 60
TEXT BOOK
1. J.E.Hopcroft, R.Motwani and J.D Ullman, “Introduction to Automata Theory, Languages and Computations”, Second Edition, Pearson Education, 2003.
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.R.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.
1. H.R.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.
0 comments:
Post a Comment