CS8501 Theory of Computation Syllabus:
CS8501 Theory of Computation Syllabus – Anna University Regulation 2017
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
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
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
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
Normal Forms for CFG — Pumping Lemma for CFL — Closure Properties of CFL — Turing Machines — Programming Techniques for TM.
UNIT V UNDECIDABILITY
Non Recursive Enumerable (RE) Language — Undecidable Problem with RE — Undecidable Problems about TM — Post?s Correspondence Problem, The Class P and NP.
TEXT BOOK:
1. J.E.Hopcroft, R.Motwani and J.D Ullman, ―Introduction to Automata Theory, Languages andComputations‖, Second Edition, Pearson Education, 2003.
REFERENCES:
1. H.R.Lewis and C.H.Papadimitriou, ―Elements of the theory of Computationl, 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.