Exemple d'un langage sans contexte qui peut néanmoins être pompé?

15

Donc, fondamentalement, L satisfait aux conditions du lemme de pompage pour les CFL mais n'est pas un CFL (ce qui est possible selon la définition du lemme).

user2329564
la source
Est-ce une question de devoirs, ou êtes-vous simplement curieux?
Yuval Filmus
Ce n'est pas un devoir mais je m'attends à le voir à l'examen (juste une intuition, connaissant mon professeur). Et je suis toujours curieux :)
user2329564
2
Nous avions une question similaire, mais pour les langues régulières . Le même type de construction s'applique: prenez un symbole spécial et considérez pour un langage méchant . $$K{$kk1}{une,b}K{une,b}
Hendrik Jan

Réponses:

13

L'exemple classique est . Wise montre dans son article Un fort lemme de pompage pour les langues sans contexte que ni le lemme de pompage de Bar-Hillel ni le théorème de Parikh (affirmant que l'ensemble des longueurs de mots dans un langage sans contexte est semi-linéaire) ne peuvent être utilisés pour prouver que n'est pas sans contexte. D'autres astuces comme l'intersection avec une langue régulière n'aident pas non plus. (Le lemme d'Ogden, une généralisation du lemme de pompage de Bar-Hillel, prouve que n'est pas dépourvu de contexte.) Il fournit également un lemme de pompage alternatif qui est équivalent à l'absence de contexte (pour les langages calculables), et l'utilise pour prouver que n'est pas sans contexte.L={unejebjck:je,j,k tous différents}LLL

Le lemme de pompage de Wise déclare qu'un langage est sans contexte si et seulement s'il y a une grammaire (non restreinte) générant et un entier tel que chaque fois que génère une "forme sententielle" (donc peut inclure des non-terminaux) de longueur , on peut écrire où sont pas vides, , et il y a un non-terminal de telle sorte que génère et génère à la fois et .G LLgLG s s | s | > k s = u v x y z x , v y | v x y | k A G u A z A v A y xkgss|s|>ks=uvXyzX,vy|vXy|kUNEguUNEzUNEvUNEyX

En appliquant à plusieurs reprises la condition dans le lemme, Wise est en mesure de prouver que n'est pas sans contexte, mais les détails sont quelque peu compliqués. Il donne également une condition équivalente encore plus compliquée et l'utilise pour prouver que le langage ne peut pas être écrit comme une intersection finie de langages sans contexte.{ a n b a n m : n , m > 0 }L{unenbunenm:n,m>0}

Si vous ne pouvez pas accéder au document de Wise (il est derrière un mur payant), il existe une version dactylographiée qui est sortie sous forme de rapport technique de l'université de l'Indiana.


Un langage non contextuel qui satisfait la condition de pompage du lemme d'Ogden est donné par Johnsonbaugh et Miller, Converse of pumping lemmas , et y est attribué à Boasson et Horvath, On languages ​​satisfying lemma d'Ogden . La langue en question est On peut écrire , correspondant aux deux lignes différentes. Notez que et que est régulier. Le lemme d'Ogden peut être utilisé pour prouver queL=L1L2L 1L2=L2L1LL

L=n1(e+une++)n(e+b++)n(e+c++)n(une+b+c+)ΣΣ(une+b+c+e)Σ(e+(une+b+c)+(une+b+c)e)Σ.
L=L1L2L1L2=L2L1n'est pas sans contexte, et donc non plus , mais il ne peut pas être utilisé directement pour montrer que n'est pas sans contexte.LL
Yuval Filmus
la source
N'est-il pas nécessaire qu'il y ait au moins une production ressemblant à ceci: A -> sententialForm1 A sententialForm2 pour que tout pompage soit possible
user2329564
Bien plus général: n'est-il pas nécessaire qu'un B non terminal fasse partie d'une forme sententielle dérivable de A telle que B-> sententialForm1.B.sententialfrom2 soit une production de G. Sinon, comment serait-il certain qu'un mot d'un une longueur arbitraire peut être pompée depuis A.
user2329564
Je ne vois pas pourquoi, nous avons une production , qui correspond au pompage. Par exemple, vous récupérez immédiatement le lemme de pompage depuis . S u A z u v i A y i z u v i x y iA+vAySuAzuviAyizuvixyiz
Yuval Filmus
4
Cela ressemble à un bel ajout à notre référence .
Raphael
Une autre chose qui manque là-bas est la fermeture sous "mappings gsm inverse", voir planetmath.org/generalizedsequentialmachine . Je vais peut-être les ajouter à un moment donné.
Yuval Filmus
8

Encore plus simple: . Peut toujours pomper le s; l'intersection avec le régulier donne un non-CFL (et cela peut être prouvé en pompant le lemme).a L ( a b + c + d + ){ambncndn:m1,n1}aL(ab+c+d+)

vonbrand
la source
1
Ce sera un bel ajout au troisième devoir ... muahaha
Renato Sanhueza
1
Je ne pense pas que ce soit juste. Si la langue commence par un seul , alors si vous essayez de pomper le vous devez tenir compte du fait qu'un doit également être dans la langue. a a 0aaa0
MCT
Pour développer le commentaire de MCT: considérons le mot ; choisissez , , . Ensuite, pour , n'est pas dans la langue, car il ne commence pas par un a, donc le lemme ne tient pas. v = a u = w = x = ε y = b p c p d p i = 0 u v i w x i yabpcpdpv=uneu=w=X=εy=bpcppje=0uvjewXjey
potestasity
2

Un langage simple est . Intersectez avec L ( a b + c + d + ) pour obtenir un clairement non-CFL, mais vous pouvez toujours pomper le et mimétiser la longueur égale dans la mer de .{unebncnn:n1}L(uneune+b+c++)L(uneb+c++)une+

vonbrand
la source
L'exemple de Wise est (apparemment) également immunisé contre ces techniques, ou du moins prétend-il.
Yuval Filmus
4
@YuvalFilmus, semble-t-il. Mais mon exemple est à l'abri des professeurs doutant que vous ayez compris le document de Wise, ou voulant une preuve complète qu'il ne s'agit pas d'une LCF dans la limite de 2 heures de l'examen ;-)
vonbrand