next up previous contents
Siguiente: Problema de intersección libre Un nivel arriba: Algunos otros problemas irresolubles Anterior: Algunos otros problemas irresolubles

Problema de complemento libre de contexto (PCLC)




Instancia:
\begin{pagi}{34}Una gram\'atica libre de contexto $G$\space sobre un alfabeto terminal $A$ .\end{pagi}
Solución:
\begin{pagi}{34}$\left\{\begin{array}{ll} 1 &\mbox{\rm si $A^*- L(G)$\space es ... ...de contexto, } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$\end{pagi}



Proposición 3.9   PCLC es irresoluble.

Demostración: Sea G la gramática libre de contexto que genera a las computaciones inválidas de M. Tenemos pues que A*- L(G) 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 PCLC es irresoluble.



Guillermo Morales-Luna
2000-07-10