Course Contents

Regular Languages & Finite Automata: Regular Languages and Regular Expressions, Deterministic and Non-deterministic Finite Automata, Kleene’s Theorem, Pumping Lemma, Myhill-Nerode Theorem. (12 lectures, 4 tutorials)

Introduction to Context-free Languages & Pushdown Automata: Context-free 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, Church-Turing Thesis, Chomsky Hierarchy, Universal Turing Machines. Recursive and Recursively Enumerable Languages. Non-recursive Languages and Undecidable Problems, the Halting Problem. Reduction (12 lectures, 4 tutorials)

Complexity: Resource-bounded computation, Classes P and NP, Polynomial time reductions, NP-completeness. (9 lectures, 3 tutorials)

Learning Outcomes

After completion of this course, a student will be able to

  1. Give the mathematical definition of various computational models and state and prove their limitations.
  2. To explain important notions in computing like nondeterminism, reductions and resource boundedness.

Text Books

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

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

References

  1. Elements of Computation Theory by Arindama Singh, Springer-Verlag London, 2009. ISBN: 978-1-4471-6142-4.

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

  3. Elements of the Theory of Computation by H. R. Lewis and C.H. Papadimitriou, Prentice Hall Publishers, 1981. ISBN-13: 978-0132624787.

Past Offerings

  • Offered in Aug-Nov, 2023 by Krishnamoorthy Dinesh
  • Offered in Aug-Dec, 2022 by Krishnamoorthy Dinesh
  • Offered in Jul-Dec, 2021 by Deepak
  • Offered in Jul-Dec, 2020 by Deepak

Course Metadata

Item Details
Course Title Theory of Computation
Course Code CS5017
Course Credits 3-1-0-4
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.