next up previous contents
Siguiente: Problema de regularidad (PR) Un nivel arriba: Reducción de problemas al Anterior: Problema de equivalencia (PE)

Problema de inclusión (PI)




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



Proposición 3.6   PC es irresoluble.


Guillermo Morales-Luna
2000-07-10