Les langues sans contexte dans

20

Les langages sans contexte ne sont pas fermés sous complément, nous le savons.

Pour autant que je sache, les langages sans contexte qui sont un sous-ensemble de pour certaines lettres sont fermés sous complément (!?) a , baba,b

Voici mon argument. Chaque langue CF a une image Parikh semi-linéaire . Les ensembles semi-linéaires sont fermés sous complément. L'ensemble des vecteurs qui représentent l'ensemble semi-linéaire peut facilement être transformé en une grammaire linéaire.π ( L ) = { ( m , n ) a m b nL }Lπ(L)={(m,n)ambnL}

Question. Y a-t-il une référence facilement accessible à ce fait?

Techniquement, ces langages sont appelés bornés , c'est-à-dire un sous-ensemble de w1wk pour certains mots w1,,wk .

Ma motivation pour cette question vient d'une question récente sur la non-contextualité de {anbmn2m} . Son complément au sein d' semble plus facile à manipuler.ab

Hendrik Jan
la source
Avez-vous vérifié la théorie mathématique des langues sans contexte de Ginsburg? Apparemment, le théorème 5.4.2 donne la caractérisation des langages sans contexte bornés dont vous parlez, et je parie que Ginsburg mentionnerait l'implication pour compléter les langages sans contexte bornés (dans le cas bidimensionnel).
Yuval Filmus

Réponses:

12

Cette caractérisation des langages sans contexte bornés est due à Ginsburg ("La théorie mathématique des langages sans contexte"), et apparaît comme Corollaire 5.3.1 dans son livre. Pour le général, kil existe des restrictions sur les ensembles semi-linéaires, mais pour k2 ces restrictions sont toujours satisfaites, et il est donc simple de déduire que le complément d'un tel langage (dans ) est sans contexte .w1w2

Ginsburg mentionne ces implications dans son livre.

Corollaire 5.6.1 Si et sont des langues [sans contexte], et mots, alors est une langue [sans contexte]. M 2 w 1 w 2 M 1M 2M1w1w2M2w1w2M1M2

Corollaire 5.6.2 Si et sont des langues [sans contexte], des mots et , alors et sont des langues [sans contexte]. M 2 w 1 w 2 M 1 - M 2 M 2 - M 1M1w1w2M2w1w2M1M2M2M1

Yuval Filmus
la source
2

Une autre preuve utilise la caractérisation suivante prouvée dans cette réponse :

Le langage est sans contexte si A est définissable dans l'arithmétique de Presburger.{aibj:(i,j)A}A

Il est clair que est définissable en arithmétique ssi Presburger ¯ A est définissable en arithmétique Presburger.AA¯

Cela montre que si les langues sont hors contexte, alors chaque expression booléenne dans les langues (impliquant l'union, l'intersection et la complémentation) est également hors contexte.Liab

Yuval Filmus
la source