TC lecture notes (draft)
Preface
This is a draft of a set of lecture notes for the Theory of Computation course at UPC. The current notes are a work in progress and are meant to be used by the students of the groups 12 and 21 of the course 2026/2027 Q1.
Please use the issue tracker to report typos, mistakes, or any other issues you find in these notes.
The content of these notes is meant to complement the lectures given in the course and the main textbook (Sipser 2013).
This set of notes is organized into chapters. Each chapter covers usually a single topic and in each lecture we will usually cover several chapters.
On the exercises
The point of view of this material is very exercise-focused. For this reason we present many exercises when they would naturally make sense (for instance to check the understanding of some definition) and not at the end of each chapter.
The exercises in this set of notes are not the ones you are assigned to solve in the racó assignment. For them please go to the course website.
Exercises are marked in different ways to highlight some of their meta properties.
| Marker | Meaning |
|---|---|
| 🌱 | Starter and warm-up exercise. You should be able to solve it in a few minutes (usually even less). If you are struggling on this type of exercises please reach out. |
| 🔥 | Hard (but doable) exercise. If you are solving an exercise with this marker, it means you should spend more time on it and possibly reach out for help/hints. |
| 🔥🔥 | Very hard exercise. We might see this type of exercise in class. |
| ✨ | Open ended and more philosophical exercise. |
| 👥 | This exercise is an in-class activity. |
| 🏔️ | Exercise with a lot of small steps that eventually will allow you to “climb-up” to a nice and very non-trivial result. |