CS21204 : Formal Language and Automata Theory Spring 2026

Schedule

Instructor     Section 1:   Aritra Hazra
Section 2:   Monosij Maitra
Timings [Slot: C4]     Monday (10:00-11:00)  |  Wednesday (08:00-10:00)  |  Thursday (10:00-11:00)
Venue     Section 1:   NC-243   [All Students with EVEN roll numbers]
Section 2:   NC-244   [All Students with ODD roll numbers]
Teaching Assistants     Anish Datta  |  Mithun Kumar Mahto  |  Sampreeth R S  |  Shivang Agrawal  |  Subhankar Jana

Notices and Announcements

December 15, 2025

This course is primarily designed as a CORE course for 2nd Year CSE students. Except these students, We are unable to admit any other UG or PG student to take part in this course. Hence, all requests from students sent via ERP will remain pending without being approved (and thereby those students are requested to switch into other courses before the subject registration deadline expires).

Tentative Coverage

Topic Details Duration
Introduction

Motivation, Strings and Languages,
Chomsky Hierarchy and Acceptors.

 2 hours
Regular Languages
and Finite Automata

DFA, NFA, Regular Expressions and their Equivalence
Pumping Lemma and Closure Properties
State Minimization and Myhill-Narode Theorem.

10 hours
Context-free Languages
and Push-down Automata

CFG and CFL, Derivations and Ambiguity
Chomsky and Greibach Normal Forms,
Pumping Lemma and Closure Properties,
Regular Grammars, PDA, DPDA and DCFL.

10 hours
Turing Machines and
Unrestricted Grammars

DTM, Equivalent Models and NTM,
Recursive and R.E. Languages,
Unrestricted Grammars and Equivalence.

5 hours
Undecidability and
Problem Reduction

Universal TM, Halting and Membership Problem,
Diagonalization and Problem Reduction,
Rice's Theorem and Decidable Problems about Languages.

6 hours
Time and Space Complexity

Time Complexity: P, NP and NP-Complete Problems
Space Complexity: PSPACE and PSPACE-Complete Problems.

4 hours
Conclusion

Models of Computation – Power, Limitation and Beyond.

1 hour

Books and References

  1. Michael Sipser; Introduction to the Theory of Computation; 3rd Edition, Cengage Publishers, 2014.    [Textbook]
  2. Dexter Kozen; Automata and Computability; Springer, 1997.    [Textbook]
  3. John E. Hopcroft and Jeffrey D. Ullman; Introduction to Automata Theory, Languages, and Computation; 1st Edition, Addison-Wesley, 1979.
  4. Harry Lewis and Christos Papadimitriou; Elements of the Theory of Computation; 2nd Edition, Pearson Education, 1997.
  5. John Martin; Introduction to Languages and the Theory of Computation; Fourth Edition, Tata McGraw-Hill, 2010.
  6. Raymond Greenlaw and H. James Hoover; Fundamentals of the Theory of Computation: Principles and Practice; Morgan Kaufmann, 1998.
  7. Daniel I. A. Cohen; Introduction to Computer Theory; Second Edition, Wiley, 1996.
  8. Dexter Kozen; Theory of Computation; Springer, 2006.
  9. Christos Papadimitriou; Computational Complexity; 1st Edition, Pearson Education, 1994.

Tutorials

Topic Date Problem-Set
Regular Languages and Finite Automata

Context-free Languages and Push-down Automata

Turing Machines and Unrestricted Grammars

(Un-)Decidability and Problem Reduction

Time and Space Complexity

Tests

Marks Distribution:   20% Class-Test + 30% Mid-Sem + 50% End-Sem