CS2200 Languages, Machines, and Computation
Jan - May 2024
Coordinates
- Where: CS15
- When: B slot - Mon (9 am), Tue (8 am), Wed (1 pm), Fri (11 am)
Instructor
- Yadu Vasudev
- SSB 207
- yadu@cse.iitm.ac.in
TAs
- Akash (cs22d012@smail)
- Balakrishnan (cs20b012@smail)
- Bhabya (cs21d200@smail)
- Kumaresan (cs21b045@smail)
- Nagashri (cs21d004@smail)
- Narayana (cs22s004@smail)
- Sampriti (cs18d200@smail)
- Subramanian (cs23m067@smail)
- Tahir (cs20b078@smail)
- Vishnu (cs23m073@smail)
Important links
- Moodle (for problem sets)
- Ed Discussions (for discussions, Q/A, announcements)
Join using your smail/iitm ids via this link - Anonymous course feedback
About this course
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.
Prerequisites - A basic course in discrete mathematics (CS1200 or equivalent) is a useful prerequisite for the course. This course is mathematical in nature, and will involve formal reasoning and writing proofs which is typically covered in CS1200.
Course 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, Church-Turing thesis.
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.
Course resources
There are many textbooks and resources (both offline and online) that cover most of the material presented in the list above. We will not be following one textbook. Our main sources of reference will be the following textbooks.
- [K]: Automata and Computability - Dexter C. Kozen
- [HMU]: Introduction to Automata Theory, Languages and Computation - Hopcroft, Motwani and Ullman, 3rd Edition
- [S]: Introduction to the Theory of Computation - Michael Sipser, 3rd Edition
All these books contain a number of exercise problems for practice.
Weekly schedule
There are three lectures per week and a tutorial. The tutorials are scheduled based on the amount of material covered in the lectures, and are ungraded. The tentative dates of the quizzes, tests, and tutorials are given below. We will try to stick to this schedule as much as possible.
Grading policy (tentative)
The course will be evaluated through a series of quizzes and finally the end-sem. I will be releasing problem sets on a weekly basis, and we will have tutorial sessions to discuss the these problems and possible approaches to solving them. The tentative grading scheme is as follows.
TipGrading pattern
- Class tests: 3*10 = 30% (best 3/4)
- Quiz 1 & 2: 2 * 15 = 30%
- End-sem: 40%
Important dates (tentative)
Please note the following dates for the ungraded tutorials and class tests. The dates for Quiz 1,2 and end-semester examination will be as per the institute calendar.
TipDates
| Tutorials | |
| Class tests | Feb 09, Mar 06, Apr |
| Quiz 1 | Feb 20 |
| Quiz 2 | Mar 19 |
| End-sem | May 07 |
Communication
Please sign up on the course discussion forum here. This will be the first point of contact for any issues related to the course. For general questions related to the course (any comments/doubts), please create a thread in the correct category and add your question/comment there. You are encouraged to reply and clear the doubts of your friends. To encourage this interaction, the forum supports anonymous posts and answers. Please be courteous to others when you are posting anonymously.
| Date | Lecture | References | Misc |
|---|---|---|---|
| Lecture #1 Wed 17/01 |
Introduction to the course • Admin and logistics • Brief history of computing |
PS0 released Register on Ed Discussions |
|
| Lecture #2 Fri 19/01 |
Languages vs problems • Alphabets, strings and languages [notes] |
|
|
| Lecture #3 Tue 23/01 |
Languages and Problems • Uncountability of the set of all languages • Machine models [notes] |
|
|
| Lecture #4 Wed 24/01 |
Programs with read-once inputs and bounded memory - states and transitions • DFAs - formal definition • Examples [notes] |
|
|
| Lecture #5 Mon 29/01 |
DFA - formal definition, notion of acceptance, regular languages, examples • Formal proof correctness of construction - examples [notes] |
|
|
| Lecture #6 Tue 30/01 |
DFA - proving correctness • Operations on languages - union, intersection, concatenation, Kleene star, examples • Closure properties of regular languages [notes] |
|
PS1 released |
| Lecture #7 Wed 31/01 |
Closure properties of regular languages - union, intersection, complement, examples • Concatenation of regular languages - the need to guess [notes] |
|
|
|
Tutorial #1 Fri 02/02 |
Based on Problem sets 0 and 1 | ||
| Lecture #8 Mon 05/02 |
Non-determinism - examples and definitions • Equivalent models - multiple start states, \( \varepsilon \)-transitions [notes] |
|
|
| Lecture #9 Tue 06/02 |
Equivalent definitions - multiple start states, \( \varepsilon \)-transitions, examples • Concatenation and Kleene star using NFAs • From NFAs to DFAs [notes] |
|
|
| Lecture #10 Wed 07/02 |
Equivalence of NFAs and DFAs - construction and examples • More closure properties using NFAs [notes] |
|
|
|
Test #1 Fri 09/02 |
Based on Lectures 1 - 7 (Problem sets 0 and 1) | ||
| Lecture #11 Mon 12/02 |
Non-regular languages - examples and proof ideas • Formalizing the idea - statement of the pumping lemma [notes] |
|
PS2 released |
| Lecture #12 Tue 13/02 |
Pumping lemma - statement and proof • Contrapositive form - examples [notes] |
|
|
| Lecture #13 Wed 14/02 |
Pumping lemma - more examples and uses [notes] |
|
|
|
Tutorial #2 Fri 16/02 |
Based on Problem set 2 | ||
| Lecture #14 Mon 19/02 |
Distinguishable and indistinguishable strings • Using distinguishable strings to prove non-regularity • Indistinguihability as an equivalence relation [notes] |
|
|
|
Quiz #1 Tue 20/02 |
Based on Lectures 1 - 13 (Problem sets 0, 1, and 2) | ||
| Lecture #15 Wed 21/02 |
Myhill-Nerode relations • Indistinguishability relation as a Myhill-Nerode relation • From DFAs to Myhill-Nerode relations [notes] |
|
|
| Lecture #16 Fri 23/02 |
From Myhill-Nerode relations to DFAs - construction, examples • Coarsest Myhill-Nerode relation [notes] |
|
|
| Lecture #17 Tue 27/02 |
Coarsest Myhill-Nerode relation • Uniqueness of minimal DFA • Quotient construction and the minimization algorithm [notes] |
|
PS3 released |
| Lecture #18 Wed 28/02 |
Quotient construction and minimization algorithm • Regular expressions [notes] |
|
|
|
Tutorial #3 Fri 01/03 |
Based on Problem set 3 | ||
| Lecture #19 Mon 04/03 |
Regular expressions - pattern matching, examples • From regular expressions to DFAs - construction, examples, complexity [notes] |
|
|
| Lecture #20 Tue 05/03 |
From DFA to regex - state elimination, examples • Decision problems on regular languages and their complexity [notes] |
|
|
|
Test #2 Wed 06/03 |
Based on Lectures 14 - 18 (Problem set 3) | ||
| Lecture #21 Mon 11/03 |
Context-Free Languages(CFL) - motivation, definition • Context-Free Grammars (CFG) - examples, derivations [notes] |
|
PS4 released |
| Lecture #22 Tue 12/03 |
Context-Free Grammars (CFG) - more examples and constructions, the Dyck language [notes] |
|
|
| Lecture #23 Wed 13/03 |
Dyck language (contd) • Regular languages and linear grammars • Parse trees [notes] |
|
|
|
Tutorial #4 Fri 15/03 |
Based on Problem set 4 | ||
| Lecture #24 Mon 18/03 |
Ambiguity in grammars - leftmost derivations and parse trees • Examples - arithmetic expressions, dangling else • Closure properties of CFLs [notes] |
|
|
|
Quiz #2 Tue 19/03 |
Based on Lectures 14 - 20 (Problem sets 3 and 4) | ||
| Lecture #25 Wed 20/03 |
Chomsky Normal Form - removing unit productions and \( \varepsilon \)-productions [notes] |
|
|
| Lecture #26 Fri 22/03 |
Chomsky Normal Form • Pumping lemma for CFLs - statement and examples [notes] |
|
PS5 released |
| Lecture #27 Tue 26/03 |
Pumping lemma for CFLs - examples • Closure properties of CFL [notes] |
|
|
|
Tutorial #5 Wed 27/03 |
Based on Problem set 5 | ||
| Lecture #28 Mon 01/04 |
Cocke-Kasami-Younger (CKY) algorithm for parsing CFGs [notes] |
|
|
| Lecture #29 Tue 02/04 |
Pushdown Automata (PDA) - definitions, acceptance conditions, examples [notes] |
|
|
| Lecture #30 Wed 03/04 |
Equivalence of PDAs and CFGs [notes] |
|
PS6 released |
|
Tutorial #6 Fri 05/04 |
Based on Problem set 6 | ||
| Lecture #31 Mon 08/04 |
Equivalence of PDAs and CFGs (contd.) • Effective computability [notes] |
|
|
| Lecture #32 Wed 10/04 |
Turing machines - motivation, definition, examples, configurations and acceptance condition [notes] |
|
|
| Lecture #33 Fri 12/04 |
Recursive and recursively enumerable languages • Multi-tape TMs • Universal TM [notes] |
|
We covered parts of these lectures. Check the notes for the exact portions |
| Lecture #34 Mon 15/04 |
Recursive and recursively enumerable languages • Membership problem (MP) and Halting problem (HP) • Enumeration machines [notes] |
|
|
|
Test #3 Tue 16/04 |
Based on Lectures 21 - 30 (Problem sets 5 and 6) | ||
| Lecture #35 Wed 17/04 |
Diagonalization - undecidability of the Halting Problem [notes] |
|
|
| Lecture #36 Thu 18/04 |
Reducibility between problems - Halting Problem, Membership Problem and other examples [notes] |
|
|
| Lecture #37 Mon 22/04 |
Many-one reductions - examples [notes] |
|
|
| Lecture #38 Tue 23/04 |
Many-one reductions - examples • Statement of Rice's theorem [notes] |
|
PS7 released |
| Lecture #39 Wed 24/04 |
Rice's theorem - examples, proof [notes] |
|
|
| Lecture #40 Thu 25/04 |
Problems on CFLs • Valid computation histories - proof ideas [notes] |
|
|
|
Tutorial #7 Fri 26/04 |
Based on Problem set 7 | ||
| Lecture #41 Mon 29/04 |
Notion of time-complexity • Efficient computation and complexity class P |
||
| Lecture #42 Tue 30/04 |
P vs NP - efficient verifiability and search • Reductions, NP-completeness • Cook-Levin theorem (statement) • Wrap-up of the course |
||
|
Test #4 Wed 01/05 |
Based on Lectures 31 - 40 (Problem set 7) | ||
|
Tutorial #8 Fri 03/05 |
Discussion of Class test 4 |
No matching items