Theory of Computation
This course offers an introduction to the theory of computation. It explores key topics such as formal models of languages, finite automata and regular languages, context-free languages, Turing machines and the theory of computability, and glimpses of computational complexity theory.
The main objective is to deepen the student’s understanding of computer science by introducing a philosophical perspective—engaging with fundamental questions like
What is computable and what is not?
and
Why are some computational problems easy, others difficult, and some impossible to solve?
The concepts and techniques presented are intentionally foundational, designed to remain relevant regardless of changes in hardware or software trends.
The course includes significant mathematical content. Students are expected to have prior experience with writing mathematical proofs and a general level of mathematical maturity. For those who meet these criteria and are curious about the theoretical limits of computation, the course promises to be both intellectually stimulating and enjoyable.
Administrative Information
- Instructors
- Antoni Lozano (email)
-
groups: 22P 22L
Office: Omega-233
Office hours: send email
- Enrique Romero (email)
-
groups: 11P 11L 12L
Office: Omega-319
Office hours: send email
For administrative questions on the course, contact one of the coordinators (Ilario Bonacina or Antoni Lozano).
Structure of the course
The main characteristic of the teaching methodology is self-learning, which is based on the use of instructional material to understand the theoretical foundations of the subject, as well as the solving of problems on the board that reinforce this theoretical knowledge.
The instructor introduces the basic theoretical foundations of each topic and solves some problems. Students learn the theory during their personal study time by reviewing the topics indicated by the instructor through the bibliography, videos, and other supplementary materials such as lecture notes, textbooks, and lists of solved problems—all freely accessible through the web.
During problem-solving sessions, students go up to the board to explain solutions to problems that were previously assigned to them. The instructor intervenes to correct a solution, clarify an argument, or highlight aspects that are considered relevant and were not fully explained by the student. The instructor also takes note of each presentation to consider it in the course assessment.
During lab sessions, students try to solve problems on the computer, which are automatically evaluated. The instructor is present to address any questions the students may have. Students may use these sessions to prepare the problems they were previously assigned, but also to study the theoretical material if they have not already done so on their own, and to ask questions about the theory.
References
The main book we will follow for the course is (Sipser 2013). Books in Catalan covering the topics of the course are (Cases and Màrquez 2003) and (Serna et al. 2004) . Videos covering most of the material of the course are available in English, Catalan, and Spanish.
- M. Sipser’s MIT video lectures
- In this course, we cover up to lecture 16 more or less (although on some topics we dig more in detail than Sipser’s lectures).
G. Godoy’s video lectures
- Teoría de lenguajes (1)
- Teoría de lenguajes (2)
- Teoría de lenguajes (3)
- Autómatas finitos deterministas
- Autómatas finitos indeterministas
- Notacions de DFAs i NFAs (1)
- Notacions de DFAs i NFAs (2)
- Operacions sobre Reg (1)
- Operacions sobre Reg (2)
- Operacions sobre Reg (3)
- Minimització de DFAs (1)
- Minimització de DFAs (2)
- Minimització de DFAs (3)
- Gramáticas incontextuales
- Operaciones sobre gramáticas
- Depuración de gramáticas (1)
- Depuración de gramáticas (2)
- Depuración de gramáticas (3)
- Expresiones regulares (1)
- Expresiones regulares (2)
- No regularidad (1)
- No regularidad (2)
- Autómatas con pila (PDA)
- Equivalencia entre CFG y PDA (1)
- Equivalencia entre CFG y PDA (2)
- Operaciones sobre PDA, y Jerarquia de Chomsky
- Maquinas de Turing (1)
- Maquinas de Turing (2)
- Equivalencia TM-programas
- Asumciones sobre TM-programas
- Operaciones sobre TM-programas
- No decidibilidad
- No semi-decidibilidad
- No computabilidad
- Accesibilidad y PCP-INI
- PCP, Intersección no vacía, ambiguedad
- No universalidad, Lógica de palabras
- Exemples de construcció d’autòmats finits (Lluís Màrquez, Enrique Romero)
- Diagonalització i no decidibilitat de K
- Problemes resolts sobre preservació de decidibilitat i semidecidibilitat
- Exercicis resolts sobre reduccions (1)
- Exercicis resolts sobre reduccions (2)
- Exercicis resolts sobre reduccions (3)
- Exercicis resolts sobre reduccions (4)
Evaluation
- Presentations at the blackboard (grade E: between 0 and 10)
- For each problem set, every student is randomly assigned one exercise to solve and present on the blackboard. The grade E takes all presentations into account.
- Midterm 1 (grade P_1: between 0 and 10)
- November 3 10:30–12:30
- Midterm 2 (grade P_2: between 0 and 10)
- January 9 08:00–11:00
- Final exam (grade F: between 0 and 10)
- January 19 11:30–14:30
- Continuous assessment (grade C: between 0 and 10)
- It is computed using the formula
C =40\%\,P_1 + 40\%\,P_2 + 20\%\,E.
There are two ways to pass this course: either without taking the final exam or by taking it. The final grade is computed differently depending on the option chosen:
Without taking the final exam, the final grade is C.
Taking the final exam, the final grade is
\max\left(F,\ 50\%\, F + 50\%\,C\right).