Course Contents
Regular Languages & Finite Automata: Regular Languages and Regular Expressions, Deterministic and Nondeterministic Finite Automata, Kleeneâ€™s Theorem, Pumping Lemma, MyhillNerode Theorem. (12 lectures, 4 tutorials)
Introduction to Contextfree Languages & Pushdown Automata: Contextfree Languages and Grammars, Ambiguity, Chomsky Normal Form, CYK Algorithm, Pumping Lemma, Introduction to Deterministic and Nondeterministic Pushdown Automata. (9 lectures, 3 tutorials)
Turing Machines & Recursive Languages: Mathematical modelling of computation, Deterministic Turing Machines, ChurchTuring Thesis, Chomsky Hierarchy, Universal Turing Machines. Recursive and Recursively Enumerable Languages. Nonrecursive Languages and Undecidable Problems, the Halting Problem. Reduction (12 lectures, 4 tutorials)
Complexity: Resourcebounded computation, Classes P and NP, Polynomial time reductions, NPcompleteness. (9 lectures, 3 tutorials)
Learning Outcomes
After completion of this course, a student will be able to
 Give the mathematical definition of various computational models and state and prove their limitations.
 To explain important notions in computing like nondeterminism, reductions and resource boundedness.
Text Books

Introduction to Languages and The Theory of Computation (4th Edition) by John C. Martin, McGrawHill Publishers, 2011. ISBN: 9780073191461.

Automata and Computability by Dexter C. Kozen. Springer Publishers 2007. ISBN: 0387949070.
References

Elements of Computation Theory by Arindama Singh, SpringerVerlag London, 2009. ISBN: 9781447161424.

Introduction to Automata Theory, Languages and Computation by Hopcroft, Motwani, and Ullman. 3rd Edition, Pearson Publishers, 2006. ISBN:0321462254.

Elements of the Theory of Computation by H. R. Lewis and C.H. Papadimitriou, Prentice Hall Publishers, 1981. ISBN13: 9780132624787.
Past Offerings
 Offered in AugNov, 2023 by Krishnamoorthy Dinesh
 Offered in AugDec, 2022 by Krishnamoorthy Dinesh
 Offered in JulDec, 2021 by Deepak
 Offered in JulDec, 2020 by Deepak
Course Metadata
Item  Details 

Course Title  Theory of Computation 
Course Code  CS5017 
Course Credits  3104 
Course Category  PMT 
Proposing Faculty  Deepak Rajendraprasad 
Approved on  Senate 11 of IIT Palakkad 
Course revision information  The syllabus of this course is the same as that of fifth semester B.Tech CS course CS3050. The examination and evaluation pattern of the two courses may differ. 