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

14

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 .GGGSSF(G)G

Soit et soit une sous-chaîne de - nous appelons un fragment de . Maintenant, laisseαSF(G)βαβSF(G)

Before(β)={γ | δ.γβδSF(G)}

et

After(β)={δ | γ.γβδ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é?Avant(β)Après(β)ggAvant(β)Après(β)

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.

Alex ten Brink
la source

Réponses:

8

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 β :Before(β)After(β)βββ

arbre avec ensembles avant et après
[ 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.ββββ


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.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,δ,S)SF(G)G=(N,T,δ,NS)

  • N={NAAN}
  • T=NT
  • δ={α(A)α(β)Aβδ}{NAAAN}

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¹.α(t)=ttTα(A)=NAaNL(G)=SF(G)Pref(SF(G))Suff(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β(NT)L(β(NT))L((NT)β)CFL

Before(β)=(Pref(SF(G))  L((NT)β))/βCFL

et

.After(β)=(Suff(SF(G))  L(β(NT)))β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.CFLPref(L)=L/ΣSuff

Raphael
la source
J'ai commencé à écrire une réponse, puis j'ai réalisé que ma preuve était la même que la vôtre. Je l' ai mis de cette façon (comprimé pour s'adapter ici): former une grammaire en ajoutant un nouveau terminal A (un metavariable) pour chaque non-terminal A et une production A A . Les formes sententielles de G sont les mots reconnus par G qui consistent en des métavariables. Il s'agit de l'intersection d'un CFG avec une langue régulière et est donc régulière. Le jeu de préfixes d'un CFG est un CFG (prenez un PDA et rendez chaque état final). B e f o r e ( γ )GA^AAA^GG est encore une CFG. Before(γ)={γγβL(Prefix(G^))}
Gilles 'SO- arrête d'être méchant'
1
@ Gilles, trois commentaires à ce sujet: 1) les formes sententielles contiennent généralement (correctement) la langue. 2) "rendre chaque état final" - cela ne fonctionnera pas; vous accepterez également les préfixes de non-mots. 3) La dernière étape de «couper» un suffixe semble difficile à obtenir rigoureuse. : / Avez-vous une épreuve rigoureuse mais plus compacte que la mienne?
Raphael
1) n'a pas d'importance (changer pour avoir ou non un terminal pour chaque terminal). 2) Oups, j'ai trop coupé: rendre chaque état qui peut atteindre un état final final. 3) Faites-le un terminal b à la fois; dans le PDA, marquez les états à partir desquels on peut atteindre un état final en consommant b comme final à la place. Oui, il faudrait plus d'expansion pour rendre cela rigoureux. Gbb
Gilles 'SO- arrête d'être méchant'
9

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:Before(β)After(β)L

Before(L,β)={γ | δ.γβδL}

et

After(L,β)={γ | δ.δβγL}

sont CF.

Before(L,β)TββTββββTβββ

βababββ

Tβ(L)=Before(L,β)Before(L,β)

After(L,β)Before(L,β)

After(L,β)=rev(Before(rev(L),rev(β)))

En fait, maintenant que je vois l'argument du renversement, il serait encore plus facile de commencer par Après(L,β), car le transducteur est plus simple à décrire et à vérifier - il génère la chaîne vide tout en recherchant un β. Quand il trouveβ il bifurque de façon non déterministe, une fourchette continue de chercher d'autres copies de β, 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-terminalX tout au long de g en disant X, déclarant X être un terminal, et ajouter toutes les productions XX à la grammaire.

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

David Lewis
la source