CS8501- THEORY OF COMPUTATION Syllabus 2017 Regulation
THEORY OF COMPUTATION CS8501- THEORY OF COMPUTATION Syllabus 2017 Regulation Syllabus 2017 Regulation
CS8501 THEORY OF COMPUTATION L T P C 3 0 0 3
- 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 :45 PERIODS
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.
- J.E.Hopcroft, R.Motwani and J.D Ullman, ―Introduction to Automata Theory, Languages and Computations‖, Second Edition, Pearson Education, 2003.
- H.R.Lewis and C.H.Papadimitriou, ―Elements of the theory of Computation, Second Edition, PHI, 2003.
- J.Martin, ―Introduction to Languages and the Theory of Computation, Third Edition, TMH, 2003.
- Micheal Sipser, ―Introduction of the Theory and Computation, Thomson Brokecole, 1997.