CS2200 - Languages, Machines and Computation

Course Timings

Slot D (Mon 11 AM, Tue 10 AM, Wed 9 AM, Thu 1 PM). Online.

Course Overview

This is the standard undergraduate core course on theory of computation. The course will introduce various abstractions of computation in the form of machines with different capabilities, and also formally introduce the notion of grammars and languages. We will also show the surprising interconnections between the two seemingly different notion of machines and languages, and this in turn will lead us to some of the most fundamental questions regarding the foundations of computation: what can and cannot be computed.

Course Contents

  • Finite Automata and Regular Languages - Finite State Automata, Regular Languages, Notion of non-determinism, Subset construction, Pattern matching and regular expressions, Closure properties, Limitations, Pumping Lemma, Myhill-Nerode relations, Quotient Construction, Minimization Algorithm.

  • Pushdown Automata and Context-free Languages - Grammars and Chomsky Hierarchy, CFLs, Regular Grammars, Chomsky Normal Form, Pumping Lemma for CFLs, Inherent Ambiguity of Context-Free Languages, Cock-Younger-Kasami Algorithm, Applications to Parsing. Pushdown Automata(PDA), PDA vs CFLs. Deterministic CFLs

  • Turing Machines and Computability - Introduction to Turing Machines, Configurations, Halting vs Looping. Multi-tape Turing machines. Recursive and Recursively enumerable languages. Undecidability of Halting Problem. Reductions. Introduction to Theory of NP-completeness.

Grading Policy

  • Bi-weekly Tests (Best 5 out of 6) (Best 4 out of 5): 30%
    • Tests on Feb 11, 25, March 11, 25, April 8, 22, May 6
  • Mid-sem Exam (April 24): 20%
  • Final Exam (May 19TBD): 70% 50%

Course Textbooks

  • Automata and Computability. Dexter C. Kozen. Springer Publishers.
  • Introduction to Automata Theory, Languages, and Computation. Hopcroft, Motwani, Ullman. Pearson Publishers 3rd Edition.
  • Introduction to the Theory of Computation. Michael Sipser. 3rd Edition.

Office Hours

  • Kartik Nagar (Instructor): Wednesday, 3-4 PM.