next up previous contents
Siguiente: Irresolubilidad en la Aritmética Un nivel arriba: Algunos otros problemas irresolubles Anterior: Problema de complemento libre

Problema de intersección libre de contexto (PILC)




Instancia:
\begin{pagi}{34}Dos gram\'aticas libres de contexto $G_1,G_2$\space sobre un mismo alfabeto terminal $A$ .\end{pagi}
Solución:
\begin{pagi}{34}$\left\{\begin{array}{ll} 1 &\mbox{\rm si $L(G_1)\cap L(G_2)$\s... ...de contexto, } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$\end{pagi}



Proposición 3.10   PILC es irresoluble.

Demostración: Sean G1 y G2 dos gramáticas libres de contexto tales que su intersección dé las computaciones terminales de M. Tenemos pues que $L(G_1)\cap L(G_2)$ es libre de contexto si y sólo si el lenguaje de M es finito. Como esto último, de acuerdo con el Teorema de Rice, es indecidible, tenemos que PILC es irresoluble.
Guillermo Morales-Luna
2000-07-10