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 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
- 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, McGraw-Hill Publishers, 2011. ISBN: 9780073191461.
-
Automata and Computability by Dexter C. Kozen. Springer Publishers 2007. ISBN: 0387949070.
References
-
Elements of Computation Theory by Arindama Singh, Springer-Verlag London, 2009. ISBN: 978-1-4471-6142-4.
-
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. 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
- Offered in July-Dec, 2019 by Deepak
Course Metadata
| Item | Details |
|---|---|
| Course Title | Theory of Computation |
| Course Code | CS3050 |
| Course Credits | 3-1-0-4 |
| 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) |