Videos
In this course, we cover the material in M. Sipser’s MIT video lectures up to lecture 16 more or less (although on some topics we dig more in detail than Sipser’s lectures).
In Catalan/Spanish there are also available G. Godoy’s video lectures.
- 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)
- Expresiones regulares (1)
- Expresiones regulares (2)
- No regularidad (1)
- No regularidad (2)
- 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
- Diagonalització i no decidibilitat de K