08
Computabilidad

Examen parcial

Computabilidad

Semana 8 — Examen parcial

Esta semana no hay clases regulares ni laboratorio.

Temas del examen

Las semanas 1 a 7:

  • Cadenas, lenguajes y operaciones sobre lenguajes.
  • DFA y NFA: diseño, construcción del producto, construcción de subconjuntos y propiedades de cierre.
  • Expresiones regulares y las conversiones en los dos sentidos.
  • Lenguajes no regulares: lema de bombeo y cadenas distinguibles. Myhill-Nerode y minimización.
  • Gramáticas libres de contexto, ambigüedad, forma normal de Chomsky y CYK.
  • Autómatas de pila y lema de bombeo para lenguajes libres de contexto.
  • Máquinas de Turing: definición, configuraciones, decidir y reconocer, variantes y la tesis de Church-Turing.

Cómo prepararse

  1. Revisar el formato y los consejos de exams/README.md.
  2. Rehacer las preguntas de repaso de las guías 1 a 7.
  3. Practicar las conversiones a mano, con ejemplos pequeños, y comprobarlas con los programas de los laboratorios.
  4. Para cada lenguaje de los ejercicios, decidir primero en qué nivel del mapa está y con qué técnica se demuestra.
  5. Rehacer las prácticas 1 y 2 sin mirar la solución.