CS2200 Languages, Machines and Computation

Jan - May 2020

Coordinates
  • D slot: Mon (11 - 11.50 am), Tue (10 - 10.50 am), Wed (9 - 9.50 am), Thu (1 - 1.50 pm)
  • CS 36
TAs
  • Anil Kumar S (cs18d001@smail)
  • Anoop S K M (cs18d003@smail)
  • Athul M A (cs19m015@smail)
  • Govind Sankar (ee16b109@smail)
  • Sampriti Roy (cs18s007@smail)
  • Sreyas S (cs18d010@smail)
Office hours
  • Yadu: Wednesdays, 2 - 3.30 pm
Objectives
This course provides an introduction to the mathematical theory of computation. The course gives a preliminary exposure to theoretical computer science, and the formal relationships among machines and computational problems with the aim of understanding the nature of computation and its inherent limits.
Contents
The following is a brief overview of the topics that will be covered in this course. The order of the topics covered may vary.
  • Finite-State Machines and Regular Languages: Languages vs Computational problems, Deterministic and non-deterministic finite state automata, regular languages, closure properties, limitations - pumping lemma and Myhill-Nerode relations, state minimization, equivalent models, algorithmic questions.
  • Context-Free Grammars: Grammars, Chomsky hierarchy, normal forms, closure properties, limitations - pumping lemma, algorithmic questions - parsing algorithm, equivalent models - push-down automata.
  • Computability Theory - Turing machines, equivalence between different variants, Universal Turing machine, recursively enumerable and recursive sets of languages, Decidability - Halting Problem, Post's correspondence problem, Rice's theorem, Church-Turing thesis.
  • Basic Complexity Theory - Measures of complexity, complexity classes P and NP, notion of polynomial-time reducibility, NP-completeness, satisfiability and Cook's theorem.
References
  • [K]: Automata and Computability - Dexter C. Kozen.
  • [HMU]: Introduction to Automata Theory, Languages and Computation - Hopcroft, Motwani and Ullman.
  • [S]: Introduction to the Theory of Computation - Michael Sipser.
Grading policy
  • Pop quizzes: 5%
  • Short exams: 3*5 = 15%
  • Quizzes: 2*20 = 40%
  • End sem: 40%
Important dates
  • Short exams: Feb 6, Mar 12, Apr 23
  • Quizzes: Feb 20, Mar 26
  • End sem: May 6
Course materials