Les ensembles Avant et Après pour les grammaires sans contexte sont-ils toujours sans contexte?

Soit $G$ une grammaire sans contexte. Une chaîne de terminaux et de nonterminals est dit être une forme propositionnelle de si vous pouvez l' obtenir en appliquant des productions de zéro fois ou plus au symbole de début de . Let l'ensemble des formes phrastiques de .$G$$G$$G$$S$$\operatorname{SF}(G)$$G$

Soit et soit une sous-chaîne de - nous appelons un fragment de . Maintenant, laisse$\alpha \in \operatorname{SF}(G)$$\beta$$\alpha$$\beta$$\operatorname{SF}(G)$

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

et

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

Les langages et Après ( β ) sont -ils sans contexte? Et si G est sans ambiguïté? Si G est sans ambiguïté, est-ce que Before ( β ) et After ( β ) peuvent également être décrits par un langage sans contexte sans ambiguïté?$\operatorname{Before}(\beta)$$\operatorname{After}(\beta)$$G$$G$$\operatorname{Before}(\beta)$$\operatorname{After}(\beta)$

Il s'agit d'un suivi de ma question précédente , après l' échec d' une tentative antérieure de faciliter la réponse à ma question. Une réponse négative rendra la question globale sur laquelle je travaille très difficile à répondre.

Essayons d'abord de ressentir et Après ( β ) . Considérons un arbre de dérivation qui contient β ; "contient" signifie ici que vous pouvez couper des sous-arbres afin que β soit un sous-mot du front de l'arbre. Ensuite, l'ensemble avant (après) sont tous les fronts potentiels de la partie gauche (droite) de l'arbre de β :$\operatorname{Before}(\beta)$$\operatorname{After}(\beta)$$\beta$$\beta$$\beta$

^{[ source ]}

Nous devons donc construire une grammaire pour la partie alignée horizontalement (verticalement) de l'arbre. Cela semble assez facile car nous avons déjà une grammaire pour tout l'arbre; nous devons juste nous assurer que toutes les formes sententielles sont des mots (changer les alphabets), filtrer celles qui ne contiennent pas (c'est une propriété régulière car β est fixe) et tout couper après (avant) β , y compris β . Cette découpe devrait également être possible.$\beta$$\beta$$\beta$$\beta$

Passons maintenant à une preuve formelle. Nous allons transformer la grammaire comme indiqué et utiliser les propriétés de fermeture de pour effectuer le filtrage et la découpe, c'est-à-dire que nous effectuons une preuve non constructive.$\mathrm{CFL}$

Soit une grammaire sans contexte. Il est facile de voir que SF ( G ) est sans contexte; construire G ′ = ( N ′ , T ′ , δ ′ , N S ) comme ceci:$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\}$

avec pour tout t ∈ T et α ( A ) = N A pour tout un ∈ N . Il est clair que L ( G ′ ) = SF ( G ) ; par conséquent, la fermeture de préfixe correspondante Pref ( SF ( G ) ) et la fermeture de suffixe Suff ( SF ( G ) ) sont également sans contexte¹.$\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))$

Maintenant, pour tout sont L ( β ( N ∪ T ) ∗ ) et L ( ( N ∪ T ) ∗ β ) les langues régulières. Comme C F L est fermé sous l'intersection et le quotient droit / gauche avec les langues régulières, nous obtenons$\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}$

et

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

¹ est fermé sous le quotient droit (et gauche) ; Pref ( L ) = L / Σ ∗ et similaire pour le préfixe de rendement Suff resp. fermeture du suffixe.$\mathrm{CFL}$$\operatorname{Pref}(L) = L / \Sigma^*$$\operatorname{Suff}$

Oui, et After ( β ) sont des langues sans contexte. Voici comment je le prouverais. Tout d'abord, un lemme (qui est le nœud). Si L est CF alors:$\mbox{Before}(\beta)$$\mbox{After}(\beta)$$L$

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

et

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

sont CF.

$\mbox{Before}(L,\beta)$$T_{\beta}$$\beta$$T_{\beta}$$\beta$$\beta$$\beta$$T_{\beta}$$\beta$$\beta$

$\beta$$abab$$\beta$$\beta$

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

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

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

En fait, maintenant que je vois l'argument du renversement, il serait encore plus facile de commencer par $\mbox{After}(L,\beta)$, car le transducteur est plus simple à décrire et à vérifier - il génère la chaîne vide tout en recherchant un $\beta$. Quand il trouve$\beta$ il bifurque de façon non déterministe, une fourchette continue de chercher d'autres copies de $\beta$, l'autre fork copiant textuellement tous les caractères suivants de l'entrée vers la sortie, acceptant tout le temps.

Il ne reste plus qu'à faire en sorte que cela fonctionne aussi bien pour les formes sententielles que pour les LFC. Mais c'est assez simple, car le langage des formes sententielles d'un CFG est lui-même un CFL. Vous pouvez montrer qu'en remplaçant chaque non-terminal$X$ tout au long de $G$ en disant $X^\prime$, déclarant $X$ être un terminal, et ajouter toutes les productions $X^\prime \rightarrow X$ à la grammaire.

Je vais devoir réfléchir à votre question sur l’ambiguïté.