CDS 303: Theory of Computation

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 ; DFA-to-Moore 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 and its Applications ; Equivalence of Regular Expressions and Regular Languages

• Lecture 24 (18.09.2026): Pumping Lemma for Regular Languages ; Applications of Pumping Lemma ; Limitations of Pumping Lemma

• Lecture 25 (18.09.2026): Recognising Non-Regular Languages: Closure Properties, Homomorphism, Fooling-Set Method, Unary Periodicity

• Lecture 26 (21.09.2026): Context-Free Grammars (CFG) and Languages (CFL): Definitions, examples, sentential forms, parse trees, ambiguity

• Lecture 27 (22.09.2026): Simplification of CFG: Eliminating null productions / unit productions / useless symbols / left recursion, Substitution rule

• Lecture 28 (25.09.2026): Chomsky Normal Form (CNF), CFG-to-CNF conversion ; Greibach Normal Form (GNF), CFG-to-GNF conversion

• Lecture 29 (25.09.2026): DFA-to-CFG conversion ; CFG membership test: CYK Algorithm

• Lecture 30 (28.09.2026): Pumping Lemma for CFL ; Applications of Pumping Lemma ; Limitations of Pumping Lemma

• Lecture 31 (29.09.2026): Closure and non-closure properties of CFL ; Inherent Ambiguity of CFL

• Lecture 32 (02.10.2026): Decidable and undecidable properties of CFL ; Applications of the Post Correspondence Problem

• Lecture 33 (05.10.2026): Nondeterministic Pushdown Automata (NPDA): Definition, Examples

• Lecture 34 (27.10.2026): Deterministic Pushdown Automata (DPDA): Definition, Examples ; DFA-to-DPDA conversion

• Lecture 35 (29.10.2026): Equivalence of Acceptance in PDA by Empty Stack and Final State

• Lecture 36 (30.10.2026): Equivalence Between CFG and PDA

• Lecture 37 (02.11.2026):

• Lecture 38 (03.11.2026):

• Lecture 39 (06.11.2026):

• Lecture 40 (09.11.2026):

• Lecture 41 (10.11.2026):

• Lecture 42 (13.11.2026):

• Lecture 43 (16.11.2026):

• Lecture 44 (17.11.2026):

• Lecture 45 (20.11.2026):