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 pp, 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 { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} no es regular y que { anbncn }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n \,\} no es libre de contexto. Lo demás se demuestra.

Convenciones del curso

  • Tablas de autómatas: la flecha →\to 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 ε\varepsilon.
  • Construcción de subconjuntos: la de la semana 2. El estado inicial es E({q0})E(\{q_0\}) y cada transición termina con una clausura ε\varepsilon. Solo se construyen los subconjuntos alcanzables. Cada subconjunto se nombra con sus estados entre llaves, en el orden del NFA, como {q0,q2}\{q_0, q_2\}. La tabla tiene una fila por subconjunto, en el orden en que aparecen, y de cada uno se calcula primero a\mathtt{a} y después b\mathtt{b}.
  • Thompson: las seis piezas de la semana 3, cada una con una entrada y una salida. Los estados se numeran q0,q1,…q_0, q_1, \ldots 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 qiniq_{\text{ini}} y qfinq_{\text{fin}}; una flecha que no está lleva ∅\emptyset; al eliminar qkq_k, cada flecha pasa a ser Rij∪Rik(Rkk)∗RkjR_{ij} \cup R_{ik}(R_{kk})^*R_{kj}.
  • Minimización: primero se quitan los estados inalcanzables. P0={F,Q−F}P_0 = \{F, Q - F\}, 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 S0S_0. Al partir una regla larga de AA, la variable nueva se llama A1A_1; la variable del terminal a\mathtt{a} se llama UaU_a.
  • CYK: los símbolos de la cadena se numeran desde 0, y T[i][j]T[i][j] tiene las variables que generan wi⋯wjw_i \cdots w_j. La tabla se llena por longitudes crecientes.
  • Autómatas de pila: la etiqueta a,b→ca, b \to c quiere decir “lee aa, saca bb, pone cc”, y cualquiera de los tres puede ser ε\varepsilon. Una configuración es (q,x,γ)(q, x, \gamma): 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 L\mathrm{L} en la primera celda deja el cabezal donde está. Una casilla vacía de la tabla lleva a qrejectq_{\text{reject}}. Una configuración se escribe u q vu\,q\,v, con el cabezal sobre el primer símbolo de vv.
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 AA el lenguaje de las cadenas sobre {0,1}\{\mathtt{0}, \mathtt{1}\} que tienen al menos dos ceros y terminan en 1\mathtt{1}. Por ejemplo, 001\mathtt{001} y 01011\mathtt{01011} están en AA, y 011\mathtt{011} y 100\mathtt{100} no.

a) Diseñen un DFA de cuatro estados que reconozca AA. 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 ”δ∗(q0,w)=q\delta^*(q_0, w) = q 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 L(M)=AL(M) = A de las cuatro afirmaciones?

c) Otra manera de llegar a un DFA para AA es el producto de un DFA de tres estados para “al menos dos ceros” con uno de dos estados para “termina en 1\mathtt{1}”. ¿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 NN, sobre {a,b}\{\mathtt{a}, \mathtt{b}\}:

δ\delta a\mathtt{a} b\mathtt{b} ε\varepsilon
→q0\to q_0 {q1}\{q_1\} ∅\emptyset {q2}\{q_2\}
q1q_1 {q1,q2}\{q_1, q_2\} {q3}\{q_3\} ∅\emptyset
∗  q2* \; q_2 ∅\emptyset {q0}\{q_0\} ∅\emptyset
q3q_3 {q2}\{q_2\} ∅\emptyset {q1}\{q_1\}

a) Calculen E({q0})E(\{q_0\}) y E({q3})E(\{q_3\}). Después sigan NN con la cadena abba\mathtt{abba}: 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 NN. 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 NN acepta bab\mathtt{bab} y si acepta aab\mathtt{aab}, 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 a(b∪a∗)\mathtt{a}(\mathtt{b} \cup \mathtt{a}^*) 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 aa\mathtt{aa}, anotando los estados activos.

b) Este DFA reconoce las cadenas sobre {a,b}\{\mathtt{a}, \mathtt{b}\} que no contienen abb\mathtt{abb}:

δ\delta a\mathtt{a} b\mathtt{b}
→∗  q0\to * \; q_0 q1q_1 q0q_0
∗  q1* \; q_1 q1q_1 q2q_2
∗  q2* \; q_2 q1q_1 q3q_3
q3q_3 q3q_3 q3q_3

Conviértanlo en una expresión regular eliminando los estados en el orden q3q_3, q2q_2, q1q_1, q0q_0. 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 q3q_3 no cambia ninguna flecha? Muestren cómo forma su expresión la cadena babab\mathtt{babab}: qué trozo de la cadena le toca a cada parte.

Pregunta 4 — Un lenguaje que no es regular

Tiempo estimado: 9 min

Sea L={ aibj:i≥2j }L = \{\, \mathtt{a}^i\mathtt{b}^j : i \geq 2j \,\}: primero las a\mathtt{a}, después las b\mathtt{b}, y al menos el doble de a\mathtt{a} que de b\mathtt{b}.

a) Demuestren con el lema de bombeo que LL no es regular.

b) Con la misma cadena que eligieron, ¿por qué no sirve el exponente i=2i = 2? Y si en lugar de esa cadena eligieran a3pbp\mathtt{a}^{3p}\mathtt{b}^p, ¿con qué división se defiende el adversario, sea cual sea el exponente?

c) Demuestren otra vez que LL 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,b}\{\mathtt{a}, \mathtt{b}\}:

δ\delta a\mathtt{a} b\mathtt{b}
→q0\to q_0 q1q_1 q0q_0
q1q_1 q2q_2 q4q_4
q2q_2 q5q_5 q3q_3
∗  q3* \; q_3 q1q_1 q0q_0
q4q_4 q1q_1 q4q_4
q5q_5 q2q_2 q3q_3
∗  q6* \; q_6 q6q_6 q3q_3

a) ¿Qué estados son inalcanzables?

b) Minimícenlo. Escriban P0P_0 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 q1q_1 de q0q_0. ¿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 ≡L\equiv_L para el lenguaje LL 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 L={ aibj:i≥2j }L = \{\, \mathtt{a}^i\mathtt{b}^j : i \geq 2j \,\} de la pregunta 4 no es regular, pero sí es libre de contexto.

a) Una gramática para LL es

S→aS∣aaSb∣εS \to \mathtt{a}S \mid \mathtt{aa}S\mathtt{b} \mid \varepsilon

No hace falta que demuestren que genera LL. Muestren que es ambigua: den dos derivaciones por la izquierda de aaab\mathtt{aaab} y digan en qué se diferencian sus árboles. ¿Cuántos árboles tiene aaaab\mathtt{aaaab}?

b) Den una gramática para LL que no sea ambigua, y con ella una derivación de aaaaabb\mathtt{aaaaabb}.

c) Justifiquen las dos cosas sobre su gramática de b): que genera exactamente LL, 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 GG la gramática

S→aSb∣TT→cT∣ε\begin{aligned} S &\to \mathtt{a}S\mathtt{b} \mid T \\ T &\to \mathtt{c}T \mid \varepsilon \end{aligned}

a) Escriban L(G)L(G) como un conjunto, en una línea.

b) Conviertan GG 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 accb\mathtt{accb}. 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 accb\mathtt{accb} 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 PP tiene los estados q0,…,q5q_0, \ldots, q_5, el alfabeto de entrada {a,b,c}\{\mathtt{a}, \mathtt{b}, \mathtt{c}\} y el alfabeto de pila {x,y,$}\{\mathtt{x}, \mathtt{y}, \texttt{\textdollar}\}. Su estado inicial es q0q_0 y su único estado de aceptación es q5q_5. Estas son todas sus transiciones:

De A Etiqueta
q0q_0 q1q_1 ε,ε→$\varepsilon, \varepsilon \to \texttt{\textdollar}
q1q_1 q1q_1 a,ε→x\mathtt{a}, \varepsilon \to \mathtt{x}
q1q_1 q2q_2 ε,ε→ε\varepsilon, \varepsilon \to \varepsilon
q2q_2 q2q_2 b,x→ε\mathtt{b}, \mathtt{x} \to \varepsilon
q2q_2 q3q_3 ε,ε→ε\varepsilon, \varepsilon \to \varepsilon
q3q_3 q3q_3 b,ε→y\mathtt{b}, \varepsilon \to \mathtt{y}
q3q_3 q4q_4 ε,ε→ε\varepsilon, \varepsilon \to \varepsilon
q4q_4 q4q_4 c,y→ε\mathtt{c}, \mathtt{y} \to \varepsilon
q4q_4 q5q_5 ε,$→ε\varepsilon, \texttt{\textdollar} \to \varepsilon

a) Escriban una ejecución de PP que acepte abbc\mathtt{abbc}, configuración por configuración.

b) ¿Qué lenguaje reconoce PP? Digan qué hace cada estado y justifiquen las dos direcciones en pocas líneas.

c) ¿En qué transiciones usa PP el no determinismo, y qué está adivinando en la que importa? Expliquen por qué ninguna ejecución acepta aab\mathtt{aab}.

d) Den una gramática para L(P)L(P).

Pregunta 9 — Un lenguaje que no es libre de contexto

Tiempo estimado: 10 min

Sea C={ anbmcndm:n,m≥0 }C = \{\, \mathtt{a}^n\mathtt{b}^m\mathtt{c}^n\mathtt{d}^m : n, m \geq 0 \,\}.

a) Demuestren con el lema de bombeo que CC no es libre de contexto, con el análisis por casos completo.

b) ¿En qué paso de su demostración usaron la condición ∣vxy∣≤p|vxy| \leq p? 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 B={ anbmcmdn:n,m≥0 }B = \{\, \mathtt{a}^n\mathtt{b}^m\mathtt{c}^m\mathtt{d}^n : n, m \geq 0 \,\}, que sí es libre de contexto. Den una gramática para BB. Pensando en la pila de un PDA, ¿qué diferencia entre BB y CC 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 MM tiene el alfabeto de entrada {a,b}\{\mathtt{a}, \mathtt{b}\} y el alfabeto de cinta {a,b,X,$,⊔}\{\mathtt{a}, \mathtt{b}, \mathtt{X}, \texttt{\textdollar}, \sqcup\}. Su estado inicial es q0q_0. Cada casilla de la tabla es (estado, símbolo que escribe, movimiento):

δ\delta a\mathtt{a} b\mathtt{b} X\mathtt{X} $\texttt{\textdollar} ⊔\sqcup
q0q_0 (q1,$,R)(q_1, \texttt{\textdollar}, \mathrm{R}) (q2,$,R)(q_2, \texttt{\textdollar}, \mathrm{R}) (qaccept,⊔,R)(q_{\text{accept}}, \sqcup, \mathrm{R})
q1q_1 (q1,a,R)(q_1, \mathtt{a}, \mathrm{R}) (q3,X,L)(q_3, \mathtt{X}, \mathrm{L}) (q1,X,R)(q_1, \mathtt{X}, \mathrm{R})
q2q_2 (q3,X,L)(q_3, \mathtt{X}, \mathrm{L}) (q2,b,R)(q_2, \mathtt{b}, \mathrm{R}) (q2,X,R)(q_2, \mathtt{X}, \mathrm{R})
q3q_3 (q3,a,L)(q_3, \mathtt{a}, \mathrm{L}) (q3,b,L)(q_3, \mathtt{b}, \mathrm{L}) (q3,X,L)(q_3, \mathtt{X}, \mathrm{L}) (q4,$,R)(q_4, \texttt{\textdollar}, \mathrm{R})
q4q_4 (q1,X,R)(q_1, \mathtt{X}, \mathrm{R}) (q2,X,R)(q_2, \mathtt{X}, \mathrm{R}) (q4,X,R)(q_4, \mathtt{X}, \mathrm{R}) (qaccept,⊔,R)(q_{\text{accept}}, \sqcup, \mathrm{R})

a) Escriban las configuraciones de MM con la entrada abba\mathtt{abba}, desde la inicial hasta que se detiene.

b) Escriban las configuraciones de MM con aab\mathtt{aab}. ¿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 MM? Justifiquen que se detiene con toda entrada, con una cota para la cantidad de pasos con una entrada de longitud nn.

d) Una compañera propone ahorrarse el símbolo $\texttt{\textdollar}: se quita q0q_0, el estado inicial pasa a ser q4q_4, que marca con X\mathtt{X} también la primera celda, y q3q_3 vuelve “hasta el borde izquierdo” moviéndose a la izquierda con a\mathtt{a}, con b\mathtt{b} y con X\mathtt{X}. Escriban las primeras cinco configuraciones de esa máquina con la entrada ab\mathtt{ab}. ¿Qué lenguaje reconoce? ¿Lo decide? ¿Es decidible ese lenguaje?

e) El lenguaje C={ anbmcndm }C = \{\, \mathtt{a}^n\mathtt{b}^m\mathtt{c}^n\mathtt{d}^m \,\} 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) { aibj:i≥2j y j≤3 }\{\, \mathtt{a}^i\mathtt{b}^j : i \geq 2j \text{ y } j \leq 3 \,\}

b) { anbm:n−m es muˊltiplo de 3 }\{\, \mathtt{a}^n\mathtt{b}^m : n - m \text{ es múltiplo de } 3 \,\}

c) { aibjck:k=i+j }\{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : k = i + j \,\}

d) Las cadenas sobre {a,b,c,d}\{\mathtt{a}, \mathtt{b}, \mathtt{c}, \mathtt{d}\}, en cualquier orden, que tienen tantas a\mathtt{a} como c\mathtt{c} y tantas b\mathtt{b} como d\mathtt{d}.

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 kk estados, todo NFA que reconoce ese lenguaje tiene al menos log⁡2k\log_2 k estados.

c) Si AA no es regular, entonces A∗A^* tampoco es regular.

d) Una gramática en forma normal de Chomsky no puede ser ambigua.

e) Si una máquina de Turing MM reconoce LL y se detiene con todas las cadenas de LL, entonces MM decide LL.

f) Si una máquina de Turing no determinista reconoce LL, 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 NN, 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 GG, en un archivo .cfg to_chomsky --pasos y cyk de la semana 5
8 El PDA PP, en un archivo .pda run_pda de la semana 6
9 Su gramática para BB cfg_strings de la semana 6; la demostración, con las de la sección Usar el lema: el juego
10 La máquina MM 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.