CS21004 Formal Languages and Automata Theory Spring 2020, L-T-P: 3-1-0

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)Local videoYouTube videoTutorial
Week 1 Reductions and undecidability Part 1 | Part 2 Part 1 | Part 2 Solution
Some decidable problems about Turing machines Single part Single Part
Week 2 Rice's theorems Part 1 | Part 2 Part 1 | Part 2 Solution
Nondeterministic Turing machines Single part Single Part Solution
Unrestricted grammars and Turing machines Single part Single Part Solution
Week 3 Undecidable problems about CFLs Part 1 | Part 2 | Part 3 Part 1 | Part 2 | Part 3 Solution
Extra Turing machines and modern computers Single part Single part No exercises
Clarification Session 1 [Notes] Single part Single part No exercises
Practice Exercises
Query Form

Tests

Previous course pages: 2013 | 2012 | 2011 | 2002

 CS21004 Formal Languages and Automata Theory Spring 2020, L-T-P: 3-1-0