Past editions: Fall ‘21, Spring ‘20, Fall ‘19
CS 420: Introduction to the Theory of Computation
Spring 2025
Course information
- Location: (W04-0138) Room 138, 4th floor, Wheatley
- Schedule: Tuesday, Thursday / 11:00am to 12:15pm
Instructor contact
- Email:
Tiago.Cogumbreiro@umb.edu - Office: (M03-0201-16) Room 0201-16, 3rd floor, McCormack
- Office hours: 10:00am - 11:00am Tuesday/Wednesday/Thursday (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 |
|---|---|---|---|
| 🙙 1. (HW1) Basics 🙚 | |||
| Tu, Jan 28 | 01 | Course overview; Coq intro | |
| Thu, Jan 30 | 02 | Pattern matching; reflexivity | |
| Tu, Feb 04 | 03 | Proofs by induction | |
| Thu, Feb 06 | (School closure) | ||
| 🙙 2. (HW2) Induction 🙚 | |||
| Tu, Feb 11 | 04 | Manipulating theorems; data-structures | |
| Thu, Feb 13 | 05 | Polymorphism; Constructor injectivity, explosion principle | |
| Tu, Feb 18 | 06 | Logical Connectives | |
| 🙙 3. (MT1) Logic and proving 🙚 | |||
| Thu, Feb 20 | 07 | Mini-test 1 | |
| 🙙 4. (HW3) Formal Languages 🙚 | |||
| Tu, Feb 25 | 08 | Formal languages | |
| Thu, Feb 27 | 09 | Kleene star, language equivalence | |
| Tu, Mar 04 | 10 | HW3 Recap & exercises | |
| 🙙 5. (HW4) Regular Languages 🙚 | |||
| Thu, Mar 06 | 11 | Regular expressions | |
| Tu, Mar 11 | 12 | REGEX & Nondeterministic Finite Automata | |
| Thu, Mar 13 | 13 | HW4 recap & exercises | |
| Tu, Mar 18 | (School closure) | ||
| Thu, Mar 20 | (School closure) | ||
| 🙙 6. (MT2) Regular automata 🙚 | |||
| Tu, Mar 25 | 14 | NFA ⇔ REGEX | |
| Thu, Mar 27 | 15 | Deterministic Finite Automata; NFA ⇔ DFA | |
| 🙙 7. (HW5) Context-free Languages 🙚 | |||
| Tu, Apr 01 | 16 | Pumping lemma; Non-regular languages | |
| Thu, Apr 03 | 17 | Context-free grammars | |
| Tu, Apr 08 | 18 | HW5 recap & exercises | |
| 🙙 8. (MT2) Context-free automata 🙚 | |||
| Thu, Apr 10 | 19 | Pushdown Automata | |
| Tu, Apr 15 | 20 | PDA ⇔ CFG | |
| 🙙 9. (HW6) Non-context-free languages 🙚 | |||
| Thu, Apr 17 | 21 | Pumping lemma; Non-context-free Languages; Turing Machines | |
| Tu, Apr 22 | 22 | Variants of Turing Machines | |
| Thu, Apr 24 | 23 | HW6 recap & exercises | |
| 🙙 10. (HW7) Decidability 🙚 | |||
| Tu, Apr 29 | 24 | Acceptance, emptiness and equality tests | |
| Thu, May 01 | 25 | Undecidability | |
| Tu, May 06 | 26 | Atm is undecidable | |
| 🙙 11. (HW8) Undecidability 🙚 | |||
| Thu, May 08 | 27 | Undecidable problems | |
| Tu, May 13 | 28 | Mapping reducibility | |