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

Problema de regularidad contenida (PRC)




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



Proposición 3.8   PA es irresoluble.


Guillermo Morales-Luna
2000-07-10