¿Los conjuntos Antes y Después para las gramáticas sin contexto siempre están libres de contexto?

Deje que $G$ sea ​​una gramática libre de contexto. Una serie de terminales y no terminales de $G$ se dice que es una forma de frase de $G$ si se puede obtener mediante la aplicación de las producciones de $G$ cero o más veces al símbolo inicial de $S$ . Deje $\operatorname{SF}(G)$ el conjunto de formas enunciativas de $G$ .

Supongamos que $\alpha \in \operatorname{SF}(G)$ y que $\beta$ sea ​​una subcadena de $\alpha$ : llamamos a $\beta$ un fragmento de $\operatorname{SF}(G)$ . Ahora deja

$\operatorname{Before}(\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in \operatorname{SF}(G) \}$

y

.$\operatorname{After}(\beta) = \{ \delta \ |\ \exists \gamma . \gamma \beta \delta \in \operatorname{SF}(G) \}$

¿Son los lenguajes libres de contexto y After ( β ) ? ¿Qué pasa si G no es ambiguo? Si G no es ambiguo, ¿ antes ( β ) y Después ( β ) también se pueden describir con un lenguaje libre de contexto inequívoco?$\operatorname{Before}(\beta)$$\operatorname{After}(\beta)$$G$$G$$\operatorname{Before}(\beta)$$\operatorname{After}(\beta)$

Este es un seguimiento de mi pregunta anterior , luego de un intento anterior de hacer que mi pregunta sea más fácil de responder falló. Una respuesta negativa hará que la pregunta global en la que estoy trabajando sea muy difícil de responder.

Permítanos sentir primero y Después ( β ) . Considere un árbol de derivación que contiene β ; "contiene" aquí significa que puede cortar subárboles para que β sea ​​una subpalabra del frente del árbol. Entonces, el conjunto antes (después) son todos los frentes potenciales de la parte izquierda (derecha) del árbol de β :$\operatorname{Before}(\beta)$$\operatorname{After}(\beta)$$\beta$$\beta$$\beta$

^{[ fuente ]}

Entonces, tenemos que construir una gramática para la parte del árbol alineada horizontalmente (verticalmente). Eso parece bastante fácil ya que ya tenemos una gramática para todo el árbol; solo tenemos que asegurarnos de que todas las formas oracionales sean palabras (cambiar los alfabetos), filtrar aquellas que no contienen (que es una propiedad regular ya que β es fijo) y cortar todo después (antes) de β , incluido β . Este corte también debería ser posible.$\beta$$\beta$$\beta$$\beta$

Ahora a una prueba formal. Transformaremos la gramática como se describe y utilizaremos las propiedades de cierre de para hacer el filtrado y el corte, es decir, realizamos una prueba no constructiva.$\mathrm{CFL}$

Sea una gramática libre de contexto. Es fácil ver que SF ( G ) no tiene contexto; construya G ′ = ( N ′ , T ′ , δ ′ , N S ) así:$G = (N, T, \delta, S)$$\operatorname{SF}(G)$$G'=(N',T',\delta',N_S)$

• $N' = \{N_A \mid A \in N\}$
• $T' = N \cup T$
• $\delta' = \{\alpha(A) \to \alpha(\beta)\mid A\to\beta \in \delta \} \cup \{N_A \to A \mid A\in N\}$

con para todos t ∈ T y α ( A ) = N A para todos un ∈ N . Está claro que L ( G ' ) = SF ( G ) ; por lo tanto, el prefijo de cierre correspondiente Pref ( SF ( G ) ) y el sufijo de cierre Suff ( SF ( G ) ) también están libres de contexto¹.$\alpha(t)=t$$t \in T$$\alpha(A)=N_A$$a\in N$$\mathcal{L}(G')=\operatorname{SF}(G)$$\operatorname{Pref}(\operatorname{SF}(G))$$\operatorname{Suff}(\operatorname{SF}(G))$

Ahora, para cualquier son L ( β ( N ∪ T ) ∗ ) y L ( ( N ∪ T ) ∗ β ) idiomas regulares. Como C F L está cerrado debajo de la intersección y el cociente derecho / izquierdo con idiomas regulares, obtenemos$\beta \in (N\cup T)^*$$\mathcal{L}(\beta(N\cup T)^*)$$\mathcal{L}((N\cup T)^*\beta)$$\mathrm{CFL}$

$\qquad \displaystyle \operatorname{Before}(\beta) = (\operatorname{Pref}(\operatorname{SF}(G))\ \cap\ \mathcal{L}((N\cup T)^*\beta))\,/\,\beta \in \mathrm{CFL}$

y

.$\qquad \displaystyle \operatorname{After}(\beta) = (\operatorname{Suff}(\operatorname{SF}(G))\ \cap\ \mathcal{L}(\beta(N\cup T)^*))\,\backslash\, \beta \in \mathrm{CFL}$

¹ está cerrado por debajo del cociente derecho (e izquierdo) ; Pref ( L ) = L / Σ ∗ y similar para el prefijo de rendimiento Suff resp. cierre de sufijo.$\mathrm{CFL}$$\operatorname{Pref}(L) = L / \Sigma^*$$\operatorname{Suff}$

Sí, y After ( β ) son lenguajes libres de contexto. Así es como lo probaría. Primero, un lema (que es el quid). Si L es CF entonces:$\mbox{Before}(\beta)$$\mbox{After}(\beta)$$L$

$\mbox{Before}(L,\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in L \}$

y

$\mbox{After}(L,\beta) = \{ \gamma \ |\ \exists \delta . \delta \beta \gamma \in L \}$

son CF.

¿Prueba? Para construya un transductor de estado finito no determinista T β que escanee una cadena, generando cada símbolo de entrada que vea y simultáneamente busque β de manera no determinista . Cada vez que T β ve el primer símbolo de β, se bifurca de manera no determinista y deja de emitir símbolos hasta que termina de ver β o ve que ve un símbolo que se desvía de β , deteniéndose en cualquier caso. Si T β ve $\mbox{Before}(L,\beta)$$T_{\beta}$$\beta$$T_{\beta}$$\beta$$\beta$$\beta$$T_{\beta}$$\beta$en su totalidad, acepta al detenerse, que es la única forma en que acepta. Si ve una desviación de , lo rechaza.$\beta$

El lema se puede activar para manejar casos en los que podría superponerse consigo mismo (como a b a b ; siga buscando β incluso mientras se encuentra en el escaneo para un β anterior ) o aparece varias veces (en realidad, el original no determinista bifurcación ya maneja eso). $\beta$$abab$$\beta$$\beta$

Está bastante claro que , y dado que las CFL están cerradas bajo transducción en estado finito, Before ( L , β ) es, por lo tanto, CF. $T_\beta(L) = \mbox{Before}(L,\beta)$$\mbox{Before}(L,\beta)$

Un argumento similar se aplica a , o podría hacerse con reversiones de cadena de Before ( L , β ) , las CFL también se cierran bajo reversión:$\mbox{After}(L,\beta)$$\mbox{Before}(L,\beta)$

$\mbox{After}(L,\beta) = \mbox{rev}(\mbox{Before}(\mbox{rev}(L),\mbox{rev}(\beta)))$

En realidad, ahora que veo el argumento de reversión, sería aún más fácil comenzar con , ya que el transductor para eso es más simple de describir y verificar: genera la cadena vacía mientras busca un β . Cuando encuentra β, se bifurca de manera no determinista, una bifurcación continúa buscando copias adicionales de β , la otra bifurcación copia todos los caracteres posteriores textualmente de entrada a salida, aceptando todo el tiempo.$\mbox{After}(L,\beta)$$\beta$$\beta$$\beta$

Lo que queda es hacer que esto funcione tanto para formularios condenatorios como para CFL. Pero eso es bastante sencillo, ya que el lenguaje de las formas sentenciales de un CFG es en sí mismo un CFL. Puede demostrar eso reemplazando cada no terminal a lo largo de G diciendo X ′ , declarando que X es un terminal y agregando todas las producciones X ′ → X a la gramática.$X$$G$$X^\prime$$X$$X^\prime \rightarrow X$

Tendré que pensar en su pregunta sobre la ambigüedad.