This syllabus has been revised in the recent past with the course number being the same.
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

  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.

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 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.