CS8501 Theory of Computation Anna University Syllabus Regulation 17

on

CS8501 Theory of Computation Anna University Syllabus Regulation 17

 CS8501    THEORY OF COMPUTATION   L T P C  3  0 0 3 

OBJECTIVES:   To understand the language hierarchy   To construct automata for any given pattern and find its equivalent regular expressions   To design a context free grammar for any given language   To understand Turing machines and their capability   To understand undecidable problems and NP class problems


UNIT I             AUTOMATA FUNDAMENTALS                                                                          9 Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata – Deterministic Finite Automata – Non-deterministic Finite Automata – Finite Automata with Epsilon Transitions

UNIT II          REGULAR EXPRESSIONS AND LANGUAGES                                                9  Regular Expressions – 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 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 Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Post‘s Correspondence Problem, The Class P and NP.

TOTAL :45PERIODS 
OUTCOMES:   Upon completion of the course, the students will be able to:  Construct automata, regular expression for any pattern.  Write Context free grammar for any construct.  Design Turing machines for any language.  Propose computation solutions using Turing machines.  Derive whether a problem is decidable or not.

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,     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.

Anna University Syllabus Regulation 17 (CSE Sem-5) Micro Processor and Micro Controller

Anna University Syllabus Regulation 17 (CSE Sem-5) Computer networks

Anna University Syllabus Regulation 17 (CSE Sem-5) Algebra and Number Theory 


Do You want International Scholarship? To Know more about the scholarship : Click Here

Are you a fresher and looking for Job? To know more about the Job Openings: Click Here
Click to Download Other ECE Materials: CLICK HERE

Click to Download Other CSE Materials: CLICK HERE


Click to Download MECH Materials: CLICK HERE

                                

Comments

Post a Comment