next up previous contents
Siguiente: Problema de regularidad contenida Un nivel arriba: Reducción de problemas al Anterior: Problema de inclusión (PI)

Problema de regularidad (PR)




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=L(G)$ , } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$\end{pagi}



Proposición 3.7   PR es irresoluble.


Guillermo Morales-Luna
2000-07-10