CS8501-Theory of Computation
Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata – Deterministic Finite Automata – Non-deterministic Finite Automata – Finite Automata with Epsilon Transitions
Regular Expressions – FA and Regular Expressions – Proving Languages not to be regular – Closure Properties of Regular Languages – Equivalence and Minimization of Automata.
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
Normal Forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines – Programming Techniques for TM.
Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Post‘s Correspondence Problem, The Class P and NP.
Reference Book:
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.
Text Book:
J.E.Hopcroft, R.Motwani and J.D Ullman, ―Introduction to Automata Theory, Languages and Computations‖, Second Edition, Pearson Education, 2003.
