Schedule

Instructor		Section 1: Abhijit Das Section 2: Sudeshna Kolay
Timing		Slot F4 [WED(10:00–10:55), THU(09:00–09:55), FRI(11:00–12:55)]
Venue		Section 1: NR223 [All students with odd roll numbers] Section 2: NR224 [All students with even roll numbers]
Teaching Assistants		Anindya Ganguly, Bijoy Das, Debranjan Pal, Souvik Sur

Syllabus

Introduction	Motivation, strings and languages, Chomsky hierarchy.	[2 hours]
Finite Automata	DFA, NFA, regular expressions, pumping lemma, state minimization.	[12 hours]
Context-free Languages	CFG and CFL, Chomsky and Greibach normal forms, parse trees, pumping lemma, PDA, DPDA, ambiguity.	[12 hours]
Turing Machines	TM, recursive and RE languages, equivalent models, unrestricted grammars.	[6 hours]
Undecidability	UTM, undecidable problems, reduction, Rice's theorem, undecidable problems about languages.	[8 hours]

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.

Online Material

	Topic (click for slides)	YouTube video	Tutorial
Week 1	Reductions and undecidability	Part 1 | Part 2	Solution
	Some decidable problems about Turing machines	Single Part
Week 2	Rice's theorems	Part 1 | Part 2	Solution
	Nondeterministic Turing machines	Single Part	Solution
	Unrestricted grammars and Turing machines	Single Part	Solution
Week 3	Undecidable problems about CFLs	Part 1 | Part 2 | Part 3	Solution
Extra	Turing machines and modern computers	Single part	No exercises
Clarification	Session 1 [Notes]	Single part	No exercises
Practice Exercises
Query Form

Tests

• Class Test 1: 06-Feb-2020, 06:45pm–07:45pm, F-116 (Sec 1) and F-142 (Sec 2) [Questions with solutions]
• Class Test 2
• Mid-Semester Test: 24-Feb-2020, 09:00am–11:00am, NR121, NR122, NR221, S302 [Questions with solutions]
• End-Semester Test

Previous course pages: 2013 | 2012 | 2011 | 2002