CS 204, Even Sem 2024-25, DTU
A4 Batch, 2nd Year
Tue 10-12 PM, Wed 2-3 PM, Fri 12-1 in AB4 403
Instructor: Garima Chhikara
Email: garimachhikara@dtu.ac.in
Links:
| Class No. | Date | Topic | Class Notes |
| 1 | 7 Jan 2025 | Introduction, DFA | Jan 7 |
| 2 | 8 Jan 2025 | DFA Examples | Jan 8 |
| 3 | 10 Jan 2025 | DFA Operations, NFA | Jan 10 |
| 4 | 15 Jan 2025 | NFA to DFA, Minimization of DFA | Jan 15 |
| 5 | 17 Jan 2025 | Minimization of NFA, Epsilon NFA, Epsilon NFA to NFA | Jan 17 |
| 6 | 21 Jan 2025 | Mealy and Moore Machine, Chomsky Classification | Jan 21 |
| 7 | 22 Jan 2025 | Regular Expression, Arden Theorem | Jan 22 |
| 8 | 30 Jan 2025 | Regular Language, Kleen Theorem | Jan 30 |
| 9 | 31 Jan 2025 | Closure Properties of Regular Language | Jan 31 |
| 10 | 4 Feb 2025 | Decidable Properties of Regular Language, Grammar | Feb 4 |
| 11 | 11 Feb 2025 | CFG, Ambiguity, Simplification of CFG, CNF | Feb 11 |
| 12 | 14 Feb 2025 | CFG to CNF, CFG to GNF | Feb 14 |
| 13 | 18 March 2025 | Push Down Automata (PDA) | March 18 |
| 14 | 25 March 2025 | NPDA, CFL Examples, CFG to PDA, PDA to CFG | March 25 |
| 15 | 26 March 2025 | Two Stack PDA, Closure and Decision Properties of CFL | March 26 |
| 16 | 28 March 2025 | Turing Machine (TM) | March 28 |
| 17 | 1 April 2025 | TM as Transducer, Non Halting TM, TM Modifications | April 1 |
| Section | Topic | Mapping with Videos of Previous Offering |
| Sec 1 | All | Lec 1 to 9 |
| Sec 1 | Myhill-Nerode Theorem | Link |
| Sec 2 | Regular Expression | Lec 10, 11, 12 |
| Sec 2 | Operators on Regular Expression | Link |
| Sec 2 | Algebraic Laws for Regular Expression | Link |
| Sec 2 | Kleen Theorem | Link |
| Sec 2 | Arden Theorem | Link Link Link |
| Sec 2 | Pumping Lemma for RL | Video Video Video |
| Sec 2 | Closure and Decision Properties of RL | Lec 26 |
| Sec 2 | Moore and Mealy Machine | Lec 15, 16 |
| Sec 3 | Grammar | Lec 13, 14 |
| Sec 3 | Ambiguity in CFG | Lec 23, 24 |
| Sec 3 | Simplification of CFG | Lec 21 |
| Sec 3 | CFG Normal Form: CNF, GNF | Lec 22, 23 |
| Sec 5 | PDA | Lec 16 to 20 |
| Sec 5 | Equivalence of PDA and CFG | Lec 24, 25 |
| Sec 5 | Two Stack PDA | Video Video |
| Sec 4 | Closure and Decision Properties of CFL | Lec 27 |
| Sec 4 | Pumping Lemma for CFL | Video Video Video |
| Sec 6 | All | Lec 27 to 35 |
| Sec 6 | Church's Thesis | Link |