Schedule

Instructor		Abhijit Das and Sudeshna Kolay
Timing		Slot F4: Wed 10:00–10:55, Thu 09:00–09:55 †, Fri 11:00–12:55 ‡ † (Doubt-clearance sessions) ‡ (Tutorial sessions)
Venue		Online
Teaching Assistants		G Chandan Ritvik, Ishwarkar Rohan Shankar, Kayastha Dhruv, Vivek Gupta

Syllabus and Coverage

Official Syllabus YouTube Playlists: AD | SK
Introduction	Week 1   (Jan 04 – Jan 08)
	Strings, languages, computational problems, finite representations, Chomsky hierarchy	Part 1 (scribes) | Part 2 (scribes)
	Query form
Regular Languages	Week 2   (Jan 11 – Jan 15)
	Deterministic finite automata, regular languages, closure properties	Part 1 (scribes) | Part 2 (scribes)
	Nondeterministic finite automata	Part 1 (scribes)
	Query form
Regular Languages	Week 3   (Jan 18 – Jan 22)
	Nondeterministic finite automata (continued)	Part 2 (scribes)
	Pattern matching, regular expressions, equivalence with regular languages	Part 1 | Part 2 (scribes)
	Query form
Regular Languages	Week 4   (Jan 25 – Jan 29)
	Pumping lemma for regular languages	Part 1 (scribes) | Part 2 (scribes)
	DFA state minimization	Part 1 (scribes)
	Query form
Regular Languages	Week 5   (Feb 01 – Feb 05)
	DFA state minimization	Part 2 (scribes)
	Myhill–Nerode relations, Myhill–Nerode theorem, uniqueness of minimal DFA	Part 1 (scribes) | Part 2 (scribes)
	Query form
Context-Free Languages	Week 6   (Feb 08 – Feb 12)
	Context-free grammars (CFG): Definition and examples	Part 1 (scribes) | Part 2 (scribes)
	Normal forms: Chomsky normal form (CNF), Greibach normal form (GNF), conversion to CNF	Single part (scribes)
	Query form
Context-Free Languages	Week 7   (Feb 15 – Feb 19)
	Grammars for regular languages	Single part (scribes)
	Pumping Lemma for context-free languages	Single part (scribes)
	Pushdown automata (PDA): Definition and examples	Single part (scribes)
	Query form
Context-Free Languages	Week 8   (Feb 22 – Feb 26)
	Pushdown automata: acceptance by empty stack and by final state	Single part (scribes)
	Equivalence between CFG and PDA	Single part (scribes)
	DPDA and DCFL	Single part (scribes)
	Query form
Turing Machines	Week 9   (Mar 04 – Mar 05)
	Introduction	Part 1 | Part 2 (scribes)
	Query form
Turing Machines	Week 10   (Mar 08 – Mar 12)
	Equivalent models	Single part (scribes)
	Nondeterministic Turing machines	Single part (scribes)
	Unrestricted grammars	Single part (scribes)
	Query form
Turing Machines	Week 11   (Mar 15 – Mar 19)
	Universal Turing machines, the membership problem and the halting problem, diagonalization	Single part (scribes)
	Proving undecidability and unsemidecidability by reduction	Part 1 | Part 2 (slides)
	Query form
Turing Machines	Week 12   (Mar 22 – Mar 26)
	Rice's theorems	Single part (slides)
	Some decidable problems about Turing machines	Single part (slides)
	Some decidable problems about context-free languages	Single part (slides)
	Query form
Turing Machines	Week 13   (Mar 29 – Apr 02)
	Computation-history method	Single part (slides)
	Equivalence with modern computers	Single part (slides)
	Query form

Books and References

[1]	Dexter C Kozen, Automata and Computability, Springer, 1997.
[2]	Harry R Lewis and Christos H Papadimitriou, Elements of the Theory of Computation, second edition, Prentice Hall, 1998.
[3]	John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman, Introduction to Automata Theory, Languages, and Computation, third edition, Prentice Hall, 2007.
[4]	Michael Sipser, Introduction to the Theory of Computation, third edition, Course Technology, 2005.
[5]	John Martin, Introduction to Languages and the Theory of Computation, third edition, Tata McGraw-Hill, 2003.
[6]	Daniel I A Cohen, Introduction to Computer Theory, second edition, Wiley, 1991.
[7]	Matthew Simon, Automata Theory, Allied Publishers, 1999.
[8]	Raymond Greenlaw and H James Hoover, Fundamentals of the Theory of Computation: Principles and Practice, Morgan Kaufmann, 1998.

Tests

Short Test 1 (29–Jan–2021) Questions with solutions Long Test 1 (12–Feb–2021) Syllabus: All topics covered on regular languages and finite automata Questions with solutions Programming assignment Last date of submission: 20–Mar–2021 Samples:         L6 : NFA | input | output         A6 : NFA | input | output | DFA         E6 : NFA | input | output | DFA         B   : NFA | input | output | DFA Solution | Samples for Evaluation Short Test 2 (26–Feb–2021) Questions with solutions Long Test 2 (12–Mar–2021) Syllabus: Context-free languages and pushdown automata Questions with solutions Long Test 2 (14–Apr–2021) Syllabus: Turing machines and undecidability Questions with solutions Short Test 3 (15–Apr–2021) Questions with solutions

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