Past editions: Fall ‘21, Spring ‘20, Fall ‘19
CS 420: Introduction to the Theory of Computation
Fall 2022
Course information
- Location: (Y01-1350) Room 1350, 1st floor, University Hall
- Schedule: Monday, Wednesday / 4:00pm to 5:15pm
Instructor contact
- Email:
Tiago.Cogumbreiro@umb.edu - Office: (M03-0201-16) Room 0201-16, 3rd floor, McCormack
- Office hours: 4:00pm - 5:00pm Monday/Tuesday/Wednesday (in-person)
Resources
- CS420 Supplementary Material: The Turing library (Coq)
- CS420 Supplementary Material: NFA/DFA/REGEX algorithms (Python)
- Logic Foundations exercises
Class Schedule
Note: Any lecture titles in future dates are considered tentative.
| Date | # | Lecture | Download |
|---|---|---|---|
| Mo, Sep 5 | (School closure) | ||
| ֍ (HW1) Logical Foundations ֍ | |||
| We, Sep 7 | 01 | Course overview; Coq intro | |
| Mo, Sep 12 | 02 | (HW1) Pattern matching; reflexivity | |
| We, Sep 14 | 03 | (HW1) Proofs by induction | |
| Classroom recording (S21) | |||
| Mo, Sep 19 | 04 | (HW1/HW2) Manipulating theorems; data-structures | |
| Classroom recording (S21) | |||
| We, Sep 21 | 05 | (HW2) Polymorphism; Constructor injectivity, explosion principle | |
| Mo, Sep 26 | 06 | (HW2) Logical Connectives | |
| We, Sep 28 | 07 | (HW2) Mini-test 1 recap | |
| ֍ Regular Languages ֍ | |||
| Mo, Oct 3 | 08 | Formal languages | |
| We, Oct 5 | 09 | Kleene star, language equivalence | |
| Mo, Oct 10 | (School closure) | ||
| We, Oct 12 | 10 | Recap & exercises | |
| Mo, Oct 17 | 11 | Regular expressions (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| We, Oct 19 | 12 | REGEX & Nondeterministic Finite Automata (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| Mo, Oct 24 | 13 | NFA ⇔ REGEX (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| We, Oct 26 | 14 | Deterministic Finite Automata; NFA ⇔ DFA (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| ֍ Context-free Languages ֍ | |||
| Mo, Oct 31 | 15 | Pumping lemma; Non-regular languages (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| We, Nov 2 | 16 | Context-free grammars (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| Mo, Nov 7 | 17 | Pushdown Automata (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| We, Nov 9 | 18 | PDA ⇔ CFG (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| Mo, Nov 14 | 19 | Pumping lemma; Non-context-free Languages; Turing Machines (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| We, Nov 16 | 20 | Variants of Turing Machines (no slides) | |
| Slides (S21) | |||
| Slides (S21) | |||
| ֍ Decidability ֍ | |||
| Mo, Nov 21 | 21 | Acceptance, emptiness and equality tests (HW7) | |
| We, Nov 23 | 22 | Undecidability | |
| Mo, Nov 28 | 23 | Atm is undecidable | |
| We, Nov 30 | 24 | Undecidable problems (HW8) (HW7 deadline) | |
| Mo, Dec 5 | 25 | Undecidable problems | |
| We, Dec 7 | 26 | Mapping reducibility | |
| Mo, Dec 12 | 27 | QA Session | |
| We, Dec 14 | 28 | QA Session (HW8 deadline) | |