¿Es posible que la intersección entre el lenguaje regular y el lenguaje libre de contexto sea intrínsecamente ambigua? Si es posible, dame algún ejemplo, por favor. De lo contrario, estoy buscando una prueba.
Respuesta
¿Demasiados anuncios?
Hendrik Jan
Puntos
1338
No, creo que no es posible, pero hay que trabajar un poco por sí mismo.
Si $L$ tiene una gramática libre de contexto $G$ entonces la construcción estándar de una gramática para $L\cap R$ tiene no-terminales $[A,p,q]$ donde $A$ es un no terminal para $G$ y $p,q$ representa un camino en un autómata para $R$ , haciendo así conjeturas sobre cuál sería un camino adecuado para la cadena terminal derivada. Ahora bien, si el autómata para $R$ es determinista y $G$ no es ambigua, ¿puede haber varias derivaciones para la misma cadena?
