In Semester 2, 2024-2025, I will be teaching CS 2200: Languages, Machines and Computation.
Administrative Information.
When and Where.
Classes are held on Monday 9 am, Tuesday 8 am, Wednesday 1 pm and Friday 11:00 am. Location: CSB 15.
Office Hours and Teaching Assistants.
The teaching assistants for the course are listed below.
- Pooja Kumari (lead), cs20d006@cse.iitm.ac.in
- K Dinesh Naik, CS24M018@smail.iitm.ac.in
- Sankar Vinayak E P, CS24M041@smail.iitm.ac.in
- Grishma Uday Karekar, CS24M020@smail.iitm.ac.in
- Ram Kumar R, CS24M037@smail.iitm.ac.in
- Mohammed Abdul Muqeeth, cs21b053@smail.iitm.ac.in
- Kosireddy Sampath Kumar, CS21B042@smail.iitm.ac.in
- Katikela Puneeth Kumar, cs21b040@smail.iitm.ac.in
- Kakunuri Shashank Reddy, cs21b038@smail.iitm.ac.in
- Janapati Varshita Devi, cs21b036@smail.iitm.ac.in
- Sankhavara Prasann Sanjaybhai, cs21b071@smail.iitm.ac.in
- Shankar Balajee S, CS21B075@smail.iitm.ac.in
- Mayank Mahajan, CS21B051@smail.iitm.ac.in
- Pachikura Pothuraju, CS21B062@smail.iitm.ac.in
Pre-requisites.
This is a core course for second year B.Tech students. There is no formal pre-requisite other than eligibility to attend the 4th semester of your BTech course. The informal pre-requisite is CS2100: Discrete Mathematics.
Academic Calendar.
Below is the tutorial and exam schedule for the course.
- Tutorials: Most Wednesdays, will be announced in class.
- Short Exams: Feb 5, March 5, April 2, April 30 Wednesday 1- 2 pm.
- Main Exams: Quiz 1 (18 Feb), Quiz 2 (25 March), Final (6 May)
Office Hours.
By appointment. Please send an email to shweta@cse.iitm.ac.in.
Course Description.
The objective of the course is to introduce students to the foundations of computation. We ask fundamental questions like "What does it mean for a function to be computed?", "Are all functions computable?", "Is there a way to measure the hardness of computing a function?" We will see that the above questions are deep, and in the quest for answering them we will learn some fundamental concepts such as state, transition, reduction, decidability.
Textbooks and References.
The primary textbook for the course is
Michael Sipser's "Introduction to the Theory of Computation". A useful second book is
"Automata and Computability" by Dexter Kozen. The library should have multiple copies. Some useful slides are
here.
Syllabus
The topics are broadly categorized as follows.
- Finite Automata & Regular Languages (Ch 1 of Sipser, Ch 13-16 of Kozen):Introduction to automata theory, languages and computational problems. Finite state automata, Regular Languages. Deterministic and Non-deterministic finite automata, Subset construction. Regular Expressions, Pattern Matching, pumping lemma, DFA state minimization, Myhill Nerode relations, Myhill Nerode theorem.
- Context Free Languages and Push Down Automata (Ch 2 of Sipser and Ch 20 and 27 of Kozen) :Context free grammars - Derivation trees and ambiguity -Chomsky normal form - Pushdown automata - Acceptance by empty store and final state - Equivalence between push-down automata and context-free grammars - Pumping lemma - PAREN language and its grammar - CYK algorithm - Closure properties of CFL.
- Turing machines & Computability (Ch 3, 4 and 5 of Sipser): Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Universal Turing machine - Turing recognizable and decidable - linear bounded automata. Decidability; Post's correspondence problem; Rice's theorem; decidability of membership, emptiness and equivalence problems of languages, reductions.
- Basic Complexity Theory: Measures of complexity, complexity classes P and NP, notion of polynomial-time reducibility, NP-completeness, satisfiability and the statement of Cook's theorem.
Requirements.
- 2 Quizzes: 20% each.
- Final Exam: 40%.
- Tutorials: 20% distributed over best 3 of 4 short exams.
Topicwise Class Summaries
| Lecture |
Topic |
Reference |
| Lec 1, 17 Jan |
Introduction to the course, Admin and logistics, Brief history of computing |
None |
| Lec 2, 20 Jan |
Review of countability, Q is countable, Power set always bigger |
Notes |
| Lec 3, 21 Jan |
Alphabets, strings and languages. Uncountability of the set of all languages. |
Chapter 0, Sipser. |
| Lec 4, 22 Jan |
Introduction to machine models. Examples of DFA. |
Section 1.1, Sipser |
| Lec 5, 24 Jan |
DFA formal definition, notion of acceptance, more examples |
Section 1.1, Sipser |
| Lec 6, 27 Jan |
Designing DFA |
Section 1.1, Sipser |
| Lec 7, 28 Jan |
Regular operations, closure properties |
Section 1.1, Sipser |
| Tutorial 1, 29 Jan |
All material so far |
None |
| Lec 8, 31 Jan |
Closure properties continued. |
Section 1.2, Sipser, Lecture 4 Kozen and these notes. |
| Lec 9, 3 Feb |
Introduction to non-determinism |
Section 1.2, Sipser |
| Lec 10, 4 Feb |
Nondeterministic Finite Automata |
Section 1.2, Sipser |
| Tutorial 2, 5 Feb |
All material so far |
None |
| Lec 11, 10 Feb |
Equivalence of NFA and DFA, concatenation of regular languages is regular |
Section 1.2, Sipser |
| Lec 12, 11 Feb |
Closure under star operation, Regular Expressions. |
Section 1.2, Sipser |
| Lec 12, 11 Feb |
Closure under star operation, Regular Expressions. |
Section 1.2, Sipser |
| Tutorial 3, 12 Feb |
All material so far |
None |
| Lec 13, 17 Feb |
Revision. |
None |
| Quiz 1, 18 Feb |
All material so far. |
None |
| Lec 14, 19 Feb |
Equivalence of regular expressions and finite automata. |
Section 1.3, Sipser |
| Lec 15, 21 Feb |
Pumping Lemma. |
Section 1.4, Sipser |
| Lec 16, 24 Feb |
Context Free Grammars. |
Section 2.1, Sipser |
| Lec 17, 25 Feb |
Context Free Grammars: Examples, Ambiguity. |
Section 2.1, Sipser |
| Tutorial 4, 26 Feb |
Pumping Lemma (Regular languages) and CFL. |
None |
| Lec 18, 3 March |
Chomsky Normal Form. |
Section 2.1, Sipser |
| Lec 19, 4 March |
Pushdown Automata |
Section 2.2, Sipser |
| Tutorial 5, 5 Mar |
CFL |
None |
| Lec 20, 7 March |
PDA examples |
Section 2.2, Sipser |
| Lec 21, 10 March |
Equivalence of CFG and PDA |
Section 2.2, Sipser |
| Lec 22, 11 March |
Equivalence of CFG and PDA |
Section 2.2, Sipser |
| Lec 23, 17 March |
Pumping Lemma for CFL |
Section 2.3, Sipser |
| Lec 24, 18 March |
Pumping Lemma for CFL, contd |
Section 2.3, Sipser |
| Tutorial 6, 19 Mar |
Pumping lemma and CFL |
None |
| Lec 25, 21 March |
Deterministic CFL |
Section 2.4, Sipser |
| Lec 26, 24 March |
CKY Algorithm |
Chapter 27, Kozen |
| Quiz 2, 25 March |
None |
None |
| Lec 27, 1 April |
Introduction to Turing machines |
Section 3.1, Sipser |
| Lec 28, 2 April |
Examples of Turing machines |
Section 3.1, Sipser |
| Lec 29, 4 April |
More examples of Turing machines |
Section 3.1, Sipser |
| Lec 29, 7 April |
Equivalence of Single and Multi-Tape TM |
Section 3.2, Sipser |
| Lec 30, 8 April |
Discussion of Quiz 2 solutions |
None |
| Lec 31, 11 April |
Equivalence of Deterministic and Non-Deterministic TM |
Section 3.2, Sipser |
| Lec 32, 15 April |
Church Turing thesis. Simple decidable languages |
Section 3.3, 4.1 Sipser |
| Lec 33, 16 April |
Decidable and Undecidable languages |
Section 4.1, 4.2 Sipser |
| Lec 34, 18 April |
Reducibility |
Section 5.1, Sipser |
| Lec 35, 21 April |
More on Reducibility |
Section 5.1, Sipser |
| Lec 36, 22 April |
Examples |
Section 5.1, Sipser |
| Lec 37, 25 April |
Computable Functions |
Section 5.3, Sipser |
| Lec 38, 28 April |
Time Complexity |
Section 7.1, Sipser |
| Lec 39, 29 April |
Computable Functions |
Section 7.2, 73, Sipser |
Policies and Grades.
Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help
you in solving some problems, you should mention the source in your writeup. Class participation will also be taken into account when assigning grades.
I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class plus being sent to the disciplinary committee. Read about plagiarism here.