Por CFG $G$ y expresiones regulares $R,S$: Para que la clase no $\{ \langle G,R,S \rangle: L(G) \cap L(R) = L(S) \}$ pertenecen?

Question

Realmente me gustaría su ayuda con la siguiente pregunta:

Para $G$ un contexto de libre gramática, y $R$, $S$ las expresiones regulares,

Para que la clase no $\{ \langle G,R,S \rangle : L(G) \cap L(R) = L(S) \}$ pertenecen?

Es en $R$, $RE/R$, co-$RE/R$?

Sé que la Intersección de la CFG y expresiones Regulares CFG, y para comparar dos expresiones regulares en $R$, pero no estoy seguro de cuál es la respuesta.

Gracias

Answer 1

Dada una gramática independiente del contexto $G$ y una expresión regular $R$ el idioma $L(G) \cap L(R)$ es independiente del contexto, y se puede encontrar por un algoritmo. Esto puede ser demostrado por un producto de una pushdown autómata y un autómata finito.

Por lo tanto, puede reducir el problema a la comprobación de si $L(G) = L(S)$.

Este problema es en $\mathsf{coRE}$ ya que se puede buscar contraejemplo $w \in A^{\ast}$ que es exactamente de un idioma.

Sin embargo, dada una CFG $G$, es indecidible si $L(G)=A^{\ast}$. Prueba de ello es el uso de la computación historias. Por lo tanto, el problema es indecidible, y la respuesta es $\mathsf{coRE} - \mathsf{R}$.

Usted podría preguntarse si no se podría haber restricciones en $S$ que hacen que el problema decidable. Le pregunté a esta pregunta en cstheory hace algún tiempo, y resulta que hay bastante buen criterio.