Schedule

Instructor		Abhijit Das and Sudeshna Kolay
Timing		Slot D4: Mon 12:00–12:55, Tue 10:00–11:55, Thu 08:00–08:55
Venue		Online
Teaching Assistants		Akashdeep Saha, Alpesh Kaushal, Bijoy Das, Debranjan Pal, Nikhil Kumar Singh

Coverage

Date	Topic	Local Material
04-Jan-2022	Introduction to languages and computation	Scribes
10-Jan-2022	Representation issues, operations on strings and languages	Scribes
11-Jan-2022	Limitations of computers Deterministic finite automata, regular languages	Scribes Slides
13-Jan-2022	Tutorial	Scribes
17-Jan-2022	More on DFA, the product construction	Scribes
18-Jan-2022	Nondeterministic finite automata, subset construction, ε-NFA, some closure properties	Scribes
20-Jan-2022	Tutorial
Supplement	Theory of ε-closures	Notes
24-Jan-2022	Patterns and regular expressions	Scribes
25-Jan-2022	Patterns and regular expressions (contd) Introduction to the pumping lemma	Scribes Scribes
27-Jan-2022	Tutorial	Scribes
31-Jan-2022	More on pumping lemma	Scribes
01-Feb-2022	Proving non-regularity by closure properties and ultimate preiodicity, DFA state minimization	Scribes
03-Feb-2022	Tutorial	Scribes
07-Feb-2022	DFA state minimization, DFA and equivalence relations	Scribes
08-Feb-2022	Myhill–Nerode theorem, applications Introduction to context-free grammars and languages	Scribes Scribes
10-Feb-2022	Tutorial	Scribes
14-Feb-2022	Example of CFG: Balanced parentheses Normal forms of CFG	Slides Slides
15-Feb-2022	Parse trees, pumpimg lemma for CFLs, (non-)closure properties Regular grammars	Slides Slides
17-Feb-2022	Tutorial
28-Feb-2022	Introduction to pushdown automata (PDA)	Scribes
01-Mar-2022	More on PDA: Acceptance issues, equivalence with CFG	Scribes
03-Mar-2022	Tutorial	Scribes
07-Mar-2022	PDA to CFG conversion, deterministic PDA (DPDA) and DCFL, closure properties	Scribes
08-Mar-2022	DPDA and DCFL (continued), introduction to Turing macines	Scribes
10-Mar-2022	Tutorial	Scribes
14-Mar-2022	Some models equivalent to Turing machines	Slides
15-Mar-2022	Non-deterministic Turing machines Unrestricted grammars	Slides Slides
17-Mar-2022	Tutorial	Exercises
21-Mar-2022	Universal Turing machines and diagonalization	Slides
22-Mar-2022	Reduction proofs of undecidability and unsemidecidability	Slides
24-Mar-2022	Tutorial	Exercises
28-Mar-2022	Reduction proofs of undecidability and unsemidecidability (continued)	Slides
29-Mar-2022	Rice's theorems Some decidable problems about Turing machines	Slides Slides

Books and References

We will mostly follow this textbook.

Dexter C Kozen, Automata and Computability, Springer, 1997.

Some other references are listed below.

• Harry R Lewis and Christos H Papadimitriou, Elements of the Theory of Computation, second edition, Prentice Hall, 1998.
• John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman, Introduction to Automata Theory, Languages, and Computation, third edition, Prentice Hall, 2007.
• Michael Sipser, Introduction to the Theory of Computation, third edition, Course Technology, 2005.
• John Martin, Introduction to Languages and the Theory of Computation, third edition, Tata McGraw-Hill, 2003.
• Daniel I A Cohen, Introduction to Computer Theory, second edition, Wiley, 1991.
• Matthew Simon, Automata Theory, Allied Publishers, 1999.
• Raymond Greenlaw and H James Hoover, Fundamentals of the Theory of Computation: Principles and Practice, Morgan Kaufmann, 1998.

Tests

• Test 1 (22-Feb-2022): Questions with solutions
• Test 2 (12-Apr-2022): Questions with solutions

Previous course pages: 2021 | 2020 | 2013 | 2012 | 2011 | 2002