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