Parcial de práctica — Teoría de la Computación
Temas: semanas 1 a 7 · Tiempo de trabajo estimado: 120 minutos
Este es un examen de práctica con el formato del parcial. Sirve para medir cuánto les toma cada tipo de pregunta: resuélvanlo en papel, con el reloj corriendo, y recién después comprueben sus respuestas con los programas de cada semana. Cada pregunta trae su tiempo estimado, y al final hay una tabla que dice con qué programa se comprueba cada una.
Indicaciones
- Escriban el procedimiento, no solo el resultado: es lo que después van a comparar paso a paso. Si un inciso usa un resultado anterior que les salió mal, sigan con el suyo.
- Una demostración dice primero qué afirma y qué técnica usa, y después va por pasos cortos, como en los apuntes. Una construcción dice qué se construye y por qué reconoce exactamente el lenguaje pedido.
- Con el lema de bombeo, muestren cada jugada: quién elige , qué cadena eligen ustedes, qué divisiones puede elegir el adversario y qué exponente eligen para cada una.
- Pueden usar sin demostrar lo que los apuntes ya demostraron: las propiedades de cierre, que no es regular y que no es libre de contexto. Lo demás se demuestra.
Convenciones del curso
- Tablas de autómatas: la flecha marca el estado inicial y el asterisco los estados de aceptación. En un NFA cada casilla es un conjunto de estados, y hay una columna para .
- Construcción de subconjuntos: la de la semana 2. El estado inicial es y cada transición termina con una clausura . Solo se construyen los subconjuntos alcanzables. Cada subconjunto se nombra con sus estados entre llaves, en el orden del NFA, como . La tabla tiene una fila por subconjunto, en el orden en que aparecen, y de cada uno se calcula primero y después .
- Thompson: las seis piezas de la semana 3, cada una con una entrada y una salida. Los estados se numeran en el orden en que se crean. Un símbolo crea su entrada y enseguida su salida. Una unión o una estrella crea primero su entrada, después las piezas de sus hijos, de izquierda a derecha, y al final su salida. La concatenación no crea estados.
- Eliminación de estados: se agregan y ; una flecha que no está lleva ; al eliminar , cada flecha pasa a ser .
- Minimización: primero se quitan los estados inalcanzables. , y en cada ronda dos estados siguen juntos si con cada símbolo van al mismo bloque.
- Forma normal de Chomsky: los cuatro pasos de la semana 5, en su orden. La variable inicial nueva se llama . Al partir una regla larga de , la variable nueva se llama ; la variable del terminal se llama .
- CYK: los símbolos de la cadena se numeran desde 0, y tiene las variables que generan . La tabla se llena por longitudes crecientes.
- Autómatas de pila: la etiqueta quiere decir “lee , saca , pone ”, y cualquiera de los tres puede ser . Una configuración es : el estado, lo que falta leer y la pila, con la cima a la izquierda. Se acepta por estado, con toda la entrada leída.
- Máquinas de Turing: la cinta es infinita solo hacia la derecha. Un movimiento en la primera celda deja el cabezal donde está. Una casilla vacía de la tabla lleva a . Una configuración se escribe , con el cabezal sobre el primer símbolo de .
| Parte | Preguntas | Minutos |
|---|---|---|
| A. Autómatas finitos | 1–2 | 18 |
| B. Expresiones regulares y los límites de lo regular | 3–5 | 31 |
| C. Lenguajes libres de contexto | 6–9 | 40 |
| D. Máquinas de Turing | 10 | 16 |
| E. El mapa completo | 11–12 | 15 |
| Total | 120 |
Parte A — Autómatas finitos
Pregunta 1 — Diseñar un DFA y demostrar que es correcto
Tiempo estimado: 8 min
Sea el lenguaje de las cadenas sobre que tienen al menos dos ceros y terminan en . Por ejemplo, y están en , y y no.
a) Diseñen un DFA de cuatro estados que reconozca . Den la tabla de lo que recuerda cada estado y la tabla de transiciones.
b) Escriban la afirmación de cada estado, de la forma ” si y solo si…”. Demuestren el paso inductivo solo para las cuatro casillas de los dos estados que ya vieron dos ceros. ¿Cómo sale de las cuatro afirmaciones?
c) Otra manera de llegar a un DFA para es el producto de un DFA de tres estados para “al menos dos ceros” con uno de dos estados para “termina en ”. ¿Cuántos estados tiene ese producto, y cuántos son alcanzables? Tiene más estados que el suyo: digan qué pares de estados del producto se pueden juntar, y por qué lo que distingue a los dos estados de cada par no sirve para nada.
Pregunta 2 — De NFA a DFA
Tiempo estimado: 10 min
Este es el NFA , sobre :
a) Calculen y . Después sigan con la cadena : por cada símbolo, escriban los destinos de las flechas y el conjunto de estados activos después de la clausura. ¿La acepta?
b) Apliquen la construcción de subconjuntos a . Den la tabla del DFA, con una fila por cada subconjunto alcanzable.
c) ¿Qué estados del DFA son de aceptación, y por qué esos? Con su DFA, digan si acepta y si acepta , escribiendo los estados por los que pasa.
Parte B — Expresiones regulares y los límites de lo regular
Pregunta 3 — Expresiones regulares, en las dos direcciones
Tiempo estimado: 12 min
a) Conviertan en un NFA con la construcción de Thompson. Antes de construirlo, calculen cuántos estados va a tener. Después den la lista de transiciones, con los estados numerados como dice la convención, y digan qué estados forman la pieza de cada nodo del árbol. Por último, sigan el NFA con , anotando los estados activos.
b) Este DFA reconoce las cadenas sobre que no contienen :
Conviértanlo en una expresión regular eliminando los estados en el orden , , , . Escriban primero las flechas del autómata generalizado. En cada eliminación digan quién entra, quién sale y cuál es el ciclo, y escriban las flechas que cambian.
c) ¿Por qué eliminar no cambia ninguna flecha? Muestren cómo forma su expresión la cadena : qué trozo de la cadena le toca a cada parte.
Pregunta 4 — Un lenguaje que no es regular
Tiempo estimado: 9 min
Sea : primero las , después las , y al menos el doble de que de .
a) Demuestren con el lema de bombeo que no es regular.
b) Con la misma cadena que eligieron, ¿por qué no sirve el exponente ? Y si en lugar de esa cadena eligieran , ¿con qué división se defiende el adversario, sea cual sea el exponente?
c) Demuestren otra vez que no es regular, ahora con un conjunto infinito de cadenas distinguibles dos a dos. Digan qué sufijo distingue a cada par.
Pregunta 5 — Minimizar un DFA
Tiempo estimado: 10 min
Este DFA tiene siete estados, sobre :
a) ¿Qué estados son inalcanzables?
b) Minimícenlo. Escriban y la partición después de cada ronda, y en cada ronda digan qué estados se separan y por qué.
c) Den la tabla del DFA mínimo. ¿Qué lenguaje reconoce? Descríbanlo con palabras.
d) Den el sufijo más corto que distingue a de . ¿En qué ronda se separaron, y qué tiene que ver el número de la ronda con la longitud de ese sufijo?
e) Si se refina sin quitar antes los estados inalcanzables, ¿cuántos estados salen? ¿El autómata que resulta es incorrecto?
f) ¿Cuántas clases de equivalencia tiene para el lenguaje de este autómata? Den una cadena de cada clase y, para cada par de esas cadenas, un sufijo que las distinga.
Parte C — Lenguajes libres de contexto
Pregunta 6 — Una gramática y su ambigüedad
Tiempo estimado: 8 min
El lenguaje de la pregunta 4 no es regular, pero sí es libre de contexto.
a) Una gramática para es
No hace falta que demuestren que genera . Muestren que es ambigua: den dos derivaciones por la izquierda de y digan en qué se diferencian sus árboles. ¿Cuántos árboles tiene ?
b) Den una gramática para que no sea ambigua, y con ella una derivación de .
c) Justifiquen las dos cosas sobre su gramática de b): que genera exactamente , y que cada cadena tiene una sola derivación por la izquierda. Alcanza con describir qué forma tienen todas sus derivaciones.
Pregunta 7 — Forma normal de Chomsky y CYK
Tiempo estimado: 14 min
Sea la gramática
a) Escriban como un conjunto, en una línea.
b) Conviertan a forma normal de Chomsky. Escriban la gramática después de cada uno de los cuatro pasos, y digan cuáles son las variables anulables y cuáles los pares unitarios.
c) Con la gramática convertida, llenen la tabla de CYK para . Para cada celda de longitud 2 o más, digan con qué punto de corte y qué regla entra cada variable. ¿La gramática genera la cadena? Recuperen un árbol de la tabla.
d) Sin contarlos: ¿cuántos pasos tiene la derivación de en la gramática convertida? ¿Cuántos árboles tiene esa cadena, y dónde se ve en la tabla?
Pregunta 8 — Un autómata de pila
Tiempo estimado: 8 min
El PDA tiene los estados , el alfabeto de entrada y el alfabeto de pila . Su estado inicial es y su único estado de aceptación es . Estas son todas sus transiciones:
| De | A | Etiqueta |
|---|---|---|
a) Escriban una ejecución de que acepte , configuración por configuración.
b) ¿Qué lenguaje reconoce ? Digan qué hace cada estado y justifiquen las dos direcciones en pocas líneas.
c) ¿En qué transiciones usa el no determinismo, y qué está adivinando en la que importa? Expliquen por qué ninguna ejecución acepta .
d) Den una gramática para .
Pregunta 9 — Un lenguaje que no es libre de contexto
Tiempo estimado: 10 min
Sea .
a) Demuestren con el lema de bombeo que no es libre de contexto, con el análisis por casos completo.
b) ¿En qué paso de su demostración usaron la condición ? Den una división de su cadena que no la cumple y con la que el adversario ganaría.
c) Si se intercambian los dos últimos bloques sale , que sí es libre de contexto. Den una gramática para . Pensando en la pila de un PDA, ¿qué diferencia entre y explica que uno lo sea y el otro no?
Parte D — Máquinas de Turing
Pregunta 10 — Una máquina de Turing
Tiempo estimado: 16 min
La máquina tiene el alfabeto de entrada y el alfabeto de cinta . Su estado inicial es . Cada casilla de la tabla es (estado, símbolo que escribe, movimiento):
a) Escriban las configuraciones de con la entrada , desde la inicial hasta que se detiene.
b) Escriban las configuraciones de con . ¿Qué casilla vacía de la tabla usa al final, y qué quiere decir sobre la entrada?
c) Digan en una línea qué hace cada estado. ¿Qué lenguaje decide ? Justifiquen que se detiene con toda entrada, con una cota para la cantidad de pasos con una entrada de longitud .
d) Una compañera propone ahorrarse el símbolo : se quita , el estado inicial pasa a ser , que marca con también la primera celda, y vuelve “hasta el borde izquierdo” moviéndose a la izquierda con , con y con . Escriban las primeras cinco configuraciones de esa máquina con la entrada . ¿Qué lenguaje reconoce? ¿Lo decide? ¿Es decidible ese lenguaje?
e) El lenguaje de la pregunta 9 no es libre de contexto, pero una máquina de Turing lo decide. Den una descripción de implementación de una: qué marcas usa, qué hace el cabezal en cada pasada y por qué se detiene siempre. No hace falta la tabla.
Parte E — El mapa completo
Pregunta 11 — Clasificar
Tiempo estimado: 7 min
Para cada lenguaje, digan si es regular, si es libre de contexto pero no regular, o si no es libre de contexto, y justifíquenlo en dos o tres líneas. Si es regular, den una expresión regular o un DFA. Si es libre de contexto, den una gramática o un PDA, y la razón por la que no es regular. Si no lo es, den el argumento; pueden usar los resultados de las otras preguntas de este parcial.
a)
b)
c)
d) Las cadenas sobre , en cualquier orden, que tienen tantas como y tantas como .
e) ¿Cuáles de los cuatro son decidibles? Digan con qué algoritmo.
Pregunta 12 — Verdadero o falso
Tiempo estimado: 8 min
Digan si cada afirmación es verdadera o falsa. Si es verdadera, den el argumento en dos o tres líneas. Si es falsa, den un contraejemplo concreto.
a) Si un NFA tiene un solo estado de aceptación, el DFA que da la construcción de subconjuntos también tiene uno solo.
b) Si el DFA mínimo de un lenguaje tiene estados, todo NFA que reconoce ese lenguaje tiene al menos estados.
c) Si no es regular, entonces tampoco es regular.
d) Una gramática en forma normal de Chomsky no puede ser ambigua.
e) Si una máquina de Turing reconoce y se detiene con todas las cadenas de , entonces decide .
f) Si una máquina de Turing no determinista reconoce , entonces alguna máquina de Turing determinista de una sola cinta también lo reconoce.
Cómo comprobar sus respuestas
Después de resolver en papel, escriban cada máquina y cada gramática en el formato del curso
(code/formats.md) y comparen con el programa de la semana. Los programas están en
code/week-NN/build/ después de correr make en esa carpeta.
| Pregunta | Qué escribir | Con qué comparar |
|---|---|---|
| 1 | Su DFA, en un archivo .dfa |
run_dfa de la semana 1 con cadenas de los dos lados; product para el inciso c) |
| 2 | El NFA , en un archivo .nfa |
run_nfa y subset de la semana 2 |
| 3 | La expresión, escrita a(b|a*); el DFA, en un archivo .dfa |
thompson, run_nfa y eliminate de la semana 3 |
| 4 | Nada | Su demostración, paso a paso, con las de la sección Cinco demostraciones de los apuntes |
| 5 | El DFA, en un archivo .dfa |
minimize y distinguish de la semana 4 |
| 6 | Las dos gramáticas, en archivos .cfg |
derive y show_cfg de la semana 5 |
| 7 | La gramática , en un archivo .cfg |
to_chomsky --pasos y cyk de la semana 5 |
| 8 | El PDA , en un archivo .pda |
run_pda de la semana 6 |
| 9 | Su gramática para | cfg_strings de la semana 6; la demostración, con las de la sección Usar el lema: el juego |
| 10 | La máquina y la de su compañera, en archivos .tm |
run_tm de la semana 7, con --limit para la segunda |
Lista de resultados para el parcial
Al corregir su práctica, marquen lo que ya pueden hacer. Cada línea es un resultado de aprendizaje del programa del curso, con las semanas donde se enseña y las preguntas de este parcial que lo ejercitan. Si una línea queda sin marcar, vuelvan a esas semanas y rehagan esas preguntas sin mirar los apuntes.
- Puedo diseñar un autómata finito, una expresión regular o una gramática para un lenguaje dado, y demostrar que reconoce exactamente ese lenguaje. Semanas 1, 2, 3 y 5. Preguntas 1, 6 b), 6 c), 8 d), 9 c) y 11.
- Puedo convertir entre DFA, NFA y expresiones regulares, y minimizar un DFA, a mano. Semanas 2, 3 y 4. Preguntas 2, 3 y 5.
- Puedo demostrar que un lenguaje no es regular o no es libre de contexto, con el lema de bombeo o con cadenas distinguibles. Semanas 4 y 6. Preguntas 4, 5 f), 9 y 11.
- Puedo decidir si una cadena pertenece al lenguaje de una gramática con el algoritmo CYK, y relacionar gramáticas con autómatas de pila. Semanas 5 y 6. Preguntas 7 y 8.
- Puedo describir una máquina de Turing en sus niveles de detalle, seguir su ejecución, y distinguir entre reconocer y decidir. Semana 7. Preguntas 10, 12 e) y 12 f).
- Puedo comprobar con un programa una construcción hecha a mano. Laboratorios de las semanas 1 a 7. En papel no se practica: es la tabla de la sección anterior.