Le langage des paires de mots de longueur égale dont la distance de brouillage est de 2 ou plus est-il hors contexte?

26

Le contexte linguistique suivant est-il libre?

L={uxvyu,v,x,y{0,1}+,|u|=|v|,uv,|x|=|y|,xy}

Comme indiqué par sdcvvc, un mot dans cette langue peut également être décrit comme la concaténation de deux mots de même longueur dont la distance de brouillage est de 2 ou plus.

Je pense que ce n'est pas sans contexte, mais j'ai du mal à le prouver. J'ai essayé de croiser cette langue avec une langue régulière (comme par exemple) puis j'utilise le lemme de pompage et / ou les homomorphismes mais j'obtiens toujours une langue trop compliquée à caractériser et à écrire vers le bas. 0101

Robert777
la source
Avez-vous essayé de pomper la chaîne ? 0u1x1u0x
Pål GD
Oui, mais je n'ai pas réussi à pomper cette chaîne hors de la langue (cela ne signifie pas que ce n'est pas possible, juste que je n'ai pas réussi à le faire).
Robert777
1
@ PålGD, vous auriez probablement besoin d'un moyen de "marquer" les pièces, comme 1u01x01u01x0
vonbrand
8
Cette langue peut être écrite comme où est la distance de Hamming. Notez que si nous remplaçons 2 par 1, c'est sans contexte ( cs.stackexchange.com/questions/307 ) mais l'astuce utilisée ici ne fonctionnera pas. Personnellement, je parie que ce n'est pas sans contexte. {uv:|u|=|v|,d(u,v)2}d
sdcvvc
1
@sdcvvc: Vous avez raison, l'un partitionne le en sorte que l'un des bits différents soit en et l'autre en . Je me suis trompé. uuxux
András Salamon

Réponses:

7

Remarque [2019-07-30] La preuve est fausse ... la question est plus compliquée qu'il n'y paraît.

Après une tentative ratée, c'est une autre idée.

Si nous croisons avec le langage régulier nous obtenons un langage CF.LLreg=0101010

Peut-être que nous pourrons avoir plus de chance si nous utilisons (une chaîne avec exactement 4 1s).Lreg=010101010

Soit , de manière informelle si elle peut être divisée en deux moitiés, de sorte qu'une moitié contient exactement ou les deux moitiés contiennent deux s mais leurs positions ne correspondent pas.L1=LLregwL1{0,1,3,4} 1s1

Supposons que soit CF et que soit sa grammaire sous la forme normale de Chomsky, et queL1G

w=uv=0a10b10c10d10eL1

Nous avons(longueur paire) et|u|=|v|d(u,v)2

Si nous limitons notre attention aux façons dont les quatre 1 de peuvent être générés, nous avons les trois cas montrés en haut de la figure 1. La partie centrale de la figure 1 montre le premier cas (mais les autres sont similaires) .w

entrez la description de l'image ici
Figure 1 (l'image complète peut être téléchargée ici )

Si nous choisissons et nous voyons que les zéros entre les deux paires de 1 doivent être pompables indépendamment (nœuds rouges sur la figure): en particulier, pour suffisamment grand , nous obtenons un nœud non terminal en double sur un sous-arbre interne (nœud X sur la figure 2) ou une sous-séquence répétée dans le chemin vers le premier ou le second 1 (nœud Y sur la figure 2). Notez que la figure 2 est un peu simplifiée: il peut y avoir plus de nœuds non terminaux entre les deux , mais aussi entre les deux ( mais avec qui ne produit que 0 à droite du premier 1).a=e,c=2ab,dabaXYsY...Zi...YZi

entrez la description de l'image ici
Figure 2

Nous pouvons donc fixer un arbitraire a=e=k,c=2a , puis choisir suffisamment grand b pour obtenir un nœud pompable indépendamment sur la séquence de zéros entre le premier et le second 1 . Pour la séquence de zéros entre le troisième et le quatrième 1, on peut choisir d=b!+b .
Mais 0b est pompable indépendamment donc il y a une sous-chaîne pompable pby , c'est-à-dire telle que b=xyz,|y|=p,|x|0,|z|0 etxyiz=b!+b . La chaîne que nous obtenons est:

w=0k10b!+b102k10b!+b10k

mais wL1 . Ainsi L1 n'est pas CF et enfin L n'est pas CF.

Si la preuve est correcte (???) elle peut être étendue à toutes les langues Lk={uv:|u|=|v|,d(u,v)k},k2

Vor
la source
J'ai peur que la prime expire avant que nous puissions réellement vérifier cette preuve, donc à moins que des informations drastiques ne surviennent dans les 4 prochaines heures, cela obtient les points pour être la meilleure tentative jusqu'à présent.
jmite
@jmite: ne vous inquiétez pas, il y a de fortes chances que ce soit une mauvaise tentative comme la précédente (qui a duré environ 30 minutes avant de découvrir une erreur triviale) :-) :-)
Vor
Pourquoi la distinction de cas? Les branches de la grammaire n'ont aucun rapport avec les moitiés du mot. Mais je pense que cela n'a pas d'importance; si la preuve fonctionne, cette distinction de cas n'est pas nécessaire. Regarder une grammaire supposée et utiliser la preuve du lemme de pompage au lieu du lemme lui-même est une bonne astuce (on devrait le faire plus souvent). J'ai une (vraie) préoccupation: si vous pompez une sous-chaîne de , vous obtenez 0 b + p ( i - 1 ) ; Je ne vois pas comment tu arrives en b + b ! . Ne pensez pas que cela devrait nuire à la preuve, mais mieux vaut vérifier. En outre, vous voudrez peut-être redresser certaines notations (et fautes de frappe).0b0b+p(i1)b+b!
Raphael
1
@Raphael: merci pour les commentaires. Peut-être que je me trompe, mais si vous choisissez comme longueur cible alors pour chaque longueur de pompage p , la chaîne 0 b peut être décomposée en 0 x y z , ( | x y z | = b , | y | = p b ) et peut être pompée en x y i z = b + b ! , en effet dans votre exemple p divise sûrement b !b+b!p0b0xyz,(|xyz|=b,|y|=pb)xyiz=b+b!b!, donc il y a a pour lequel p ( i - 1 ) = b ! , mais la longueur de la chaîne d'origine est b , donc la longueur totale pompée est | x y ( i - 1 ) z | = b + b ! . Je m'en souviens de quelques exercices qui utilisent le lemme d'Ogden ... maintenant je vais les vérifier. (i1)p(i1)=b!b|xy(i1)z|=b+b!
Vor
@Raphael: ... Je n'ai trouvé la preuve nulle part mais seulement un article de Zach Tomaszewski qui prouve que le complément de est CF (voir question ), donc c'est peut-être un nouveau résultat (bien que simple); et un théorème de style lemme de pompage peut être dérivé pour les langues avec des chaînes qui contiennent un nombre fini d'un symbole particulier et des sous-chaînes de longueur arbitraire entre elles. Ldup={ww}
Vor
2

Après 2 tentatives infructueuses, qui ont été réfutées par @Hendrik Jan (merci), en voici une autre, qui n'est pas plus réussie. @Vor a trouvé un exemple de langage CF déterministe où la même construction s'appliquerait, si elle était correcte. Cela a permis d'identifier une erreur dans l'ancrage de la chaîne dans l'application du lemme. Le lemme lui-même ne semble pas en cause. C'est clairement une construction trop simpliste. Voir plus de détails dans les commentaires.y


L={uxvyu,v,x,y{0,1}{ϵ} , u∣=∣v , uv , x∣=∣y , xy }

L={uv:|u|=|v|,d(u,v)2}

10i10ji<ji+jux10j10j

ppp

i=pi

Cependant, nous pourrions pomper des deux côtés du deuxième 1 aussi vite ou même plus vite du côté droit, de sorte que le deuxième 1 ne traverserait jamais le milieu de la corde. De plus, le lemme d'Ogden ne fixe pas de limite supérieure à la taille de ce qui est pompé, de sorte qu'il n'est pas possible d'organiser le pompage pour obtenir le 1 le plus à droite exactement au milieu de la chaîne.

Nous utilisons une version modifiée du lemme, appelée ici Lemme de Nash, qui peut gérer ces difficultés.

uvvvuv

Lp>0q>0wpLpwww=uxyzvuxyzv

  1. xz
  2. xyzp
  3. x^y^z^
    1. x^xy^yz^z
    2. 1≤∣x^z^∣≤q1≤∣y^∣≤q
    3. uxjx^iy^z^izjvLi0j0

yxzx^z^y^qxjzjj0j=1 simplifier la comptabilité lors de l'application du lemme.

p2qi=p+2qi=p+qz^

jjihqj=i+h

d[1,q]hkk10j10j

.

Je pense que je ne verrai jamais
Une chaîne belle comme un arbre.
Car s'il n'a pas d'analyse,
la chaîne n'est qu'une farce

babou
la source
Notez cependant que le passage sur la seconde moitié lit la pile en sens inverse. Cela semble vouloir dire que les deux positions sont dans la même position dans les deux moitiés, mais en sens inverse?
Hendrik Jan
vous avez raison ... j'ai gaffé ... maintenant je sais ce qui me harcelait à l'arrière de ma tête.
babou
J'ai reconnu l'argument (parce que je ne pouvais pas le faire fonctionner quand je me suis essayé).
Hendrik Jan
aibjckaibjck
@HendrikJan Ai-je encore gaffé? (BTW, merci d'en avoir fait une discussion)
babou
-1

LSAXBYBYAXA00A00A11A01A1B10B00B11B01B1X00X00X11X01X1Y10Y00Y11Y01Y1

MK Dadsetani
la source
4
Ceci est une erreur; vous ne pouvez pas garder cette longueur de AX est la même que BY. Par exemple, votre grammaire génère S -> AXBY -> A011 -> 0A1011 -> 001011 qui n'est pas dans la langue d'origine. De plus, vos symboles A et X génèrent le même langage, le même pour B et Y; ils peuvent être fusionnés.
sdcvvc