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.
2 . 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.
Curriculum 2017
Course Objectives:
The course will provide a formal connection between algorithmic problem solving and the theory of languages and automata and develop them into a mathematical view towards algorithmic design and in general computation itself.
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.
2 . 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.