CDS 303: Theory of Computation
Fall 2026
- Instructor: Satyabrata Jana ( satyabrataj [at] iiserbpr [dot] ac [dot] in )
- Timings: Monday (11 – 12 PM), Tuesday (12 – 1 PM), Friday (2.30 – 3.30 PM)
- Venue: Room No. 2006, 2nd Floor, Block 6
- Grading: End-Sem Exam (40%), Mid-Sem Exam (30%), Quizzes (10%), Presentation (10%), Attendance (10%)
Objectives
This course introduces the fundamental concepts of the Theory of Computation, including formal languages, automata, computability, and computational complexity. Students will study different models of computation and understand their capabilities and limitations. The course also examines the relationships among various classes of languages and computational problems. Emphasis will be placed on developing analytical reasoning, mathematical rigour, and proof-writing skills.
Prerequisites
Students are expected to be comfortable with basic mathematical reasoning, elementary set theory, functions, relations, and standard proof techniques such as induction and proof by contradiction.
References
- Introduction to the Theory of Computation – Michael Sipser
- Introduction to Automata Theory, Languages, and Computation – John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
- Automata and Computability – Dexter C. Kozen
- An Introduction to Formal Languages and Automata – Peter Linz, Susan H. Rodger
- Elements of the Theory of Computation – Harry R. Lewis, Christos H. Papadimitriou
- Introduction to Theory of Computation – Anil Maheshwari, Michiel Smid
- Automata, Computability and Complexity: Theory and Applications – Elaine Rich
- Theory of Computer Science: Automata, Languages and Computation – K. L. P. Mishra, N. Chandrasekaran
- Theory of Computation: Automata, Languages, Complexity – Supantha Pandit, Jagpreet Singh
Lectures
- Lecture 01 (04.08.2026): Mathematical Preliminaries: Sets, Relation, Functions, Logics
- Lecture 02 (07.08.2026): Formal Languages: Alphabets, Strings, Operation on Strings, Languages, Operation on Languages
- Lecture 03 (10.08.2026): Deterministic Finite Automata (DFA): Definition, Transition Functions, State Diagrams & Tables, Examples
- Lecture 04 (11.08.2026): Systematic Construction of DFA: State Design Paradigm, Product, Complement, De Morgan, Myhill–Nerode Quotient
- Lecture 05 (12.08.2026): Nondeterministic Finite Automata (NFA): Definition, Transition Functions, ε-NFA, State Diagrams & Tables, Examples
- Lecture 06 (17.08.2026): Systematic Construction of ε-NFA/NFA: State Design Paradigm, Thompson, Modular Closure, Product, De Morgan
- Lecture 07 (18.08.2026): Equivalence of ε-NFA/NFA and DFA: Rabin–Scott Subset (Powerset) Construction
- Lecture 08 (19.08.2026): From ε-NFA/NFA to Minimal DFA: Brzozowski's Double-Reversal Algorithm
- Lecture 09 (24.08.2026): From ε-NFA to NFA: ε-Closure Method, Edge-Bypass Method
- Lecture 10 (25.08.2026): State Removal in ε-NFA/NFA/DFA ; DFA Minimization: Table-Filling Method (Huffman)
- Lecture 11 (28.08.2026): DFA Minimization: Moore's Algorithm (Partition Refinement), Hopcroft's Algorithm (Efficient Partition Refinement)
- Lecture 12 (31.08.2026): Minimal-DFA uniqueness ; Myhill–Nerode Theorem: Optimality of DFA Minimization
- Lecture 13 (01.09.2026): Finite Automata with Output: Moore Machine, Mealy Machine ; Moore–Mealy Conversion
- Lecture 14 (04.09.2026): Extended Transition Function for DFA/NFA/ε-NFA ; Applications of FA: Lexical Analysis, Protocol Verification
- Lecture 15 (07.09.2026): Regular Expressions (RE): Definition, Examples, Properties
- Lecture 16 (08.09.2026): RE to ε-NFA: McNaughton–Yamada–Thompson Construction, Ilie–Yu ε-Follow Construction
- Lecture 17 (11.09.2026): RE to NFA: Glushkov’s Position Automaton, Antimirov’s Partial-Derivative Construction
- Lecture 18 (11.09.2026): RE to DFA: Brzozowski’s Derivative Method, Syntax Tree/ Followpos Methods
- Lecture 19 (14.09.2026): DFA to RE: State Elimination Method, Arden's Theorem Method, McNaughton–Yamada Method
- Lecture 20 (14.09.2026): NFA to RE: State Elimination Method, Arden's Theorem Method, McNaughton–Yamada Method
- Lecture 21 (14.09.2026): ε-NFA to RE: State Elimination Method, Arden's Theorem Method, McNaughton–Yamada Method
- Lecture 22 (15.09.2026): Regular Language: Definition, Examples, Properties
- Lecture 23 (15.09.2026): Myhill–Nerode Theorem ; Equivalence of Regular Expressions and Regular Languages
- Lecture 24 (18.09.2026): Pumping Lemma for Regular Languages ; Applications of Pumping Lemma
- Lecture 25 (19.09.2026): Higman’s Theorem, Dickson’s Theorem
- Lecture 26 (21.09.2026):
- Lecture 27 (22.09.2026):
- Lecture 28 (25.09.2026):
- Lecture 29 (28.09.2026):
- Lecture 30 (29.09.2026):
- Lecture 31 (02.10.2026):
- Lecture 32 (05.10.2026):
- Lecture 33 (06.10.2026):
- Lecture 34 (09.10.2026):