CS2200 Languages, Machines, and Computation

Jan - May 2020

Coordinates

  • Where: CS 36
  • When: D slot (Mon 11-11.50, Tue 10-10.50, Wed 9-9.50, Thu 13-13.50)

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)

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
  • Quizzes: Feb 20

Course Materials

  • Moodle
  • Lectures and references