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

Problema de equivalencia (PE)




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



Proposición 3.5   PE es irresoluble.

Demostración: En particular si consideramos una GLC G1 que genere a todo el alfabeto, si resolviéramos PE resolveríamos también PT.


La irresolubilidad de los siguientes problemas se debe a esta misma razón.
Guillermo Morales-Luna
2000-07-10