Ejercicios para la evaluación continua

Tema 8: Problemes naturals indecidibles

Fecha de publicación

Invalid Date

Leyenda

= el ejercicio ha sido asignado a un/una estudiante/a y será resuelto en clase.
Para ver la asignación (y la fecha de entrega) consulta el racó.

Ejercicio 1 Demostrad que los siguientes problemas son indecidibles reduciendo desde accesibilidad de palabras.

  1. \{\langle u,v,R\rangle|\exists w_1,w_2:u\to_R^*w_1vw_2\}.
  2. \{\langle u,v,R\rangle|u\to_R^*vv\}.
  3. \{\langle u,v,R\rangle|uu\to_R^*v\}.
  4. \{\langle u,v,w,R\rangle|u\to_R^*v\text{ sin pasar por }w\}.
  5. \{\langle u,v,R\rangle|u\to_R^*v\wedge \forall (l\to r)\in R: |l|=1\vee |r|=1\}.
  6. \{\langle u,v,R=\{l_1\to r_1,\ldots,l_n\to r_n\}\rangle\;|\; u\to_R^*v\wedge |l_1|,|r_1|,\ldots,|l_n|,|r_n|\leq 2\wedge |u|=|v|=1\}.
  7. \{\langle u,v,R\rangle|u\to_R^*v\text{ usando cada regla de $R$ al menos una vez}\}.

Ejercicio 2 Demostrad que los siguientes problemas son indecidibles reduciendo desde PCP o PCP-INI.

  1. \{\langle u_1,v_1,\ldots,u_n,v_n\rangle|n\in \dot{2}+1\wedge\exists 1\leq i_1,\ldots,i_k\leq n:(k>0\;\wedge\;u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k})\}.
  2. \{\langle u_1,v_1,\ldots,u_n,v_n\rangle|\exists 1\leq i_1,\ldots,i_k\leq n:(k\in\dot{2}\wedge u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k})\}.
  3. \{\langle u_1,v_1,\ldots,u_n,v_n\rangle|\;|u_1|,|v_1|,\ldots,|u_n|,|v_n|\in\dot{2}\wedge\exists 1\leq i_1,\ldots,i_k\leq n:(k>0\;\wedge\;u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k})\}.
  4. \{\langle u_1,v_1,\ldots,u_n,v_n\rangle|u_1,v_1,\ldots,u_n,v_n\in\{0,1\}^*\wedge\exists 1\leq i_1,\ldots,i_k\leq n:(k>0\;\wedge\;u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k})\}.

Ejercicio 3 Demostrad que los siguientes problemas son indecidibles reduciendo desde intersección vacía,o desde intersección no vacía.

  1. \{\langle G_1,G_2\rangle\mid|{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)|\geq 3\}.
  2. \{\langle G_1,G_2\rangle\mid|{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)|=3\}.
  3. \{\langle G_1,G_2\rangle\mid|{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)|=\infty\}.
  4. \{\langle G_1,G_2\rangle\mid |\mathcal{L}(G_(a)|=|\mathcal{L}(G_2)|=\infty\wedge|{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)|\not=\infty\}.
  5. \{\langle G_1,G_2\rangle\mid\Sigma_{G_1}=\Sigma_{G_2}=\{a,b\}^*\;\wedge\;{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)\not=\emptyset\wedge{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)\cap\{aa,bb\}^*=\emptyset\}.
  6. \{\langle G_1,G_2\rangle\mid{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)\not=\emptyset\wedge\not\exists w\in ({\mathcal L}(G_(a)\cap{\mathcal L}(G_2)):|w|\in\dot{2}+1\}.
  7. \{\langle G_1,G_2\rangle\mid{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)\not=\emptyset\wedge\not\exists w\in ({\mathcal L}(G_(a)\cap{\mathcal L}(G_2)):|w|\in\dot{2}\}.

Ejercicio 4 Demostrad que los siguientes problemas son indecidibles reduciendo desde no universalidad.

  1. \{G\;|\;{\mathcal L}(G)\not=\Sigma^*-\{\lambda\}\}.
  2. \{G\;|\;{\mathcal L}(G)\not=\Sigma^*-\{aab\}\}.
  3. \{G\;|\;{\mathcal L}(G)\not\supseteq(aab\Sigma^*)\}.
  4. \{G=\langle V,\Sigma,\delta,S\rangle\;|\;\Sigma=\{a,b\}\wedge{\mathcal L}(G)\not=\Sigma^*\}.
  5. \{G=\langle V,\Sigma,\delta,S\rangle\;|\;\Sigma=\{a,b\}\wedge{\mathcal L}(G)\not=(aa+bb)^*\}.
  6. \{G=\langle V,\Sigma,\delta,S\rangle\;|\;\Sigma=\{a,b\}\wedge{\mathcal L}(G)\not=(aa+bb+ab+ba)^*\}.
  7. \{G=\langle V,\Sigma,\delta,S\rangle\;|\;\Sigma=\{a,b,c\}\wedge{\mathcal L}(G)\not=\Sigma^*\}.
  8. \{G\;|\;|\overline{{\mathcal L}(G)}|=\infty\}.

Ejercicio 5 Sea L un lenguaje regular. Demuestra que o bien \{G\;|\;{\mathcal L}(G)=L\} o bien \{G\;|\;{\mathcal L}(G)=\bar{L}\} es indecidible.

Pista

Procede por reducción al absurdo suponiendo que ambos son decidibles y concluyendo que entonces universalidad es decidible.

Ejercicio 6 Demuestra que los siguientes problemas son indecidibles reduciendo desde veracidad de fórmulas de lógica de primer orden interpretadas sobre palabras.

  1. El problema de saber si una descripción de la forma \{w|F(w)\}, donde F es una fórmula de lógica de palabras con variable libre w, representa al lenguaje (a+b)^*.
  2. El problema de saber si una descripción de la forma \{w|F(w)\}, donde F es una fórmula de lógica de palabras con variable libre w, representa al lenguaje vacío.
  3. El problema de saber si una descripción de la forma \{w|F(w)\}, donde F es una fórmula de lógica de palabras con variable libre w, representa al lenguaje a^*b^*.
  4. El problema de saber si una descripción de la forma \{w|F(w)\}, donde F es una fórmula de lógica de palabras con variable libre w, representa al lenguaje de las palabras palíndromas sobre \{a,b\}.
  5. El problema de saber si una descripción de la forma \{w|F(w)\}, donde F es una fórmula de lógica de palabras con variable libre w, representa algun lenguaje finito.
  6. El problema de saber si una descripción de la forma \{w|F(w)\}, donde F es una fórmula de lógica de palabras con variable libre w, representa algun lenguaje incontextual.

Ejercicio 7 Demuestra que los siguientes problemas son decidibles:

  1. \{\langle u,v,R=\{l_1\to r_1,\ldots,l_n\to r_n\}\rangle\;|\; u\to_R^*v\wedge\forall 1\leq i\leq n:|l_i|\geq|r_i|\}.
  2. \{\langle u,v,R=\{l_1\to r_1,\ldots,l_n\to r_n\}\rangle\;|\; u\to_R^*v\wedge\forall 1\leq i\leq n:|l_i|\leq|r_i|\}.
  3. \{\langle u,v,R=\{l_1\to r_1,\ldots,l_n\to r_n\}\rangle\;|\; u\to_R^*v\wedge|R|=1\}.
  4. \{\langle u,v,R=\{l_1\to r_1,\ldots,l_n\to r_n\}\rangle\;|\; u\to_R^*v\wedge|u|,|v|,|l_1|,|r_1|,\ldots,|l_n|,|r_n|\leq 10 \wedge\Sigma=\{0,1\}\}.
  5. \{\langle u,v,R=\{l_1\to r_1,\ldots,l_n\to r_n\}\rangle\;|\; u\to_R^*v\wedge u,v,l_1,r_1,\ldots,l_n,r_n\in a^*\}.
  6. \{\langle u_1,v_1,\ldots,u_n,v_n\rangle| u_1,v_1,\ldots,u_n,v_n\in a^*\exists 1\leq i_1,\ldots,i_k\leq n: u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k}\}.
  7. \{\langle G,A\rangle\in\mathtt{CFG}\times\mathtt{DFA}\;|\; {\mathcal L}(G)\not\subseteq{\mathcal L}(A)\}.

Ejercicio 8 Completa la siguiente reducción de PCP a intersección no vacía: \langle u_1,v_1,\ldots,u_n,v_n\rangle \mapsto \langle S\to u_1Sv_1^R|\cdots|u_nSv_n^R|u_1\#v_1^R|\cdots|u_n\#v_n^R\;,\;\ldots ?\ldots\rangle.

Ejercicio 9 Cuales de los siguientes problemas pueden ser decidibles y cuales pueden ser indecidibles:

  1. \{\langle u,v\rangle\;|\; u\to_R^*v\} donde R es un sistema de reescritura fijado de antemano.
  2. \{R\;|\; u\to_R^*v\} donde u,v son palabras diferentes fijadas de antemano.
  3. \{\langle u_1,v_1,\ldots,u_n,v_n\rangle| \exists 1\leq i_1,\ldots,i_k\leq n: u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k}\} donde k es un número fijado de antemano.
  4. \{\langle u_1,v_1,\ldots,u_n,v_n\rangle| \exists 1\leq i_1,\ldots,i_k\leq n: u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k}\} donde n es un número fijado de antemano.
  5. \{G|{\mathcal L}(G)\supseteq{\mathcal L}(G')\} donde G' es una gramática fijada de antemano.
  6. \{G\in\mathtt{CFG}\;|\; {\mathcal L}(G)\not\supseteq{\mathcal L}(A)\} donde A es un DFA fijado de antemano.
  7. \{G|{\mathcal L}(G)\not\subseteq{\mathcal L}(G')\} donde G' es una gramática fijada de antemano.
  8. \{G|{\mathcal L}(G)\cap{\mathcal L}(G')\not=\emptyset\} donde G' es una gramática fijada de antemano.
Pista

En los ultimos dos piensa en la reducción de PCP a intersección no vacía del Ejercicio 8.

Ejercicio 10 Dado un sistema de reescritura R=\{l_1\to r_1,\ldots,l_n\to r_n\} sobre el alfabeto \{a,b\}, llamaremos w_R a la palabra \#l_1\$r_1\#l_2\$r_2\#\ldots\#l_n\$r_n\#, donde \# y \$ son símbolos nuevos. Esencialmente, w_R es una palabra que codifica el sistema de reescritura. Demuestra que existe una fórmula de lógica de primer orden sobre palabras F(x,y,z), donde x, y y z son variables libres, que cumple lo siguiente: dadas dos palabras u, v y un sistema de reescritura R, todos ellos sobre el alfabeto \{a,b\}, resulta que u\to_R^*v\Leftrightarrow F(u,v,w_R).

Ejercicio 11 Aprovechando el resultado del ejercicio anterior, demuestra que los siguientes problemas son indecidibles reduciendo desde veracidad de fórmulas de lógica de primer orden interpretadas sobre palabras.

  1. El problema de saber si una descripción de la forma \{w|F(w)\}, donde F es una fórmula de lógica de palabras con variable libre w, representa algun lenguaje decidible.
  2. El problema de saber si una descripción de la forma \{w|F(w)\}, donde F es una fórmula de lógica de palabras con variable libre w, representa algun lenguaje semidecidible.

Ejercicio 12 Justifica que \{G|{\mathcal L}(G)\text{ no es regular}\} es indecidible.

Pista

Retoca la reducción de PCP a intersección no vacía \langle u_1,v_1,\ldots,u_n,v_n\rangle \mapsto \langle G_1,G_2\rangle así: \langle u_1,v_1,\ldots,u_n,v_n\rangle \mapsto \langle \{a^mb^m\}\cdot G_1,\{a^mb^m\}\cdot G_2\rangle, donde a y b son símbolos nuevos. Haz lo mismo con la reducción de PCP a no-universalidad. Justifica que la gramática resultante, si no es universal, entonces el lenguaje que genera no es regular.