Showing the latest revision in section Curriculum 2022. The earlier version is in section Curriculum 2017.
Curriculum 2022
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
 Offered in JulyDec, 2019 by Deepak
Course Metadata
Item  Details 

Course Title  Theory of Computation 
Course Code  CS3050 
Course Credits  3104 
Course Category  PMC 
Proposing Faculty  Deepak Rajendraprasad 
Approved on  Senate 20 of IIT Palakkad 
Course prerequisites  Discrete Mathematics 
Course status  revised 
Course revision information  Existing Course  Theory of Computation CS3050 (B.Tech, CSE) and CS5017 (MCaM) 