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

Le contexte linguistique suivant est-il libre?

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.$\ 0^*1^*0^*1^*$

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.$L$$L_{reg} = 0^*10^*10^*10^*$

Peut-être que nous pourrons avoir plus de chance si nous utilisons (une chaîne avec exactement 4 1s).$L_{reg}' = 0^*10^*10^*10^*10^*$

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.$L_1 = L \cap L_{reg}'$$w \in L_1$$\{0,1,3,4\}$ $1s$$1$

Supposons que soit CF et que soit sa grammaire sous la forme normale de Chomsky, et que$L_1$$G$

Nous avons(longueur paire) et$|u|=|v|$$d(u,v) \geq 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$

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=2a$$b,d \gg a$$b \gg a$$X$$Ys$$Y\to ... \to Z_i \to ... Y$$Z_i$

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 $0^b$ est pompable indépendamment donc il y a une sous-chaîne pompable $p \leq b$$y$ , c'est-à-dire telle que $b = xyz, |y|=p, |x|\geq 0, |z|\geq 0$ et$xy^iz = b!+b$ . La chaîne que nous obtenons est:

mais $w' \notin L_1$ . Ainsi $L_1$ n'est pas CF et enfin $L$ n'est pas CF.

Si la preuve est correcte (???) elle peut être étendue à toutes les langues $L_k = \{ uv : |u|=|v|, d(u,v)\geq k\}, k\geq 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 = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ \}$

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

$10^i10^j$$i \lt j$$i+j$$u$$x$$10^j10^j$

$p$$p$$p$

$i=p$$i$

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.

$u$$v$$v$$v$$u \prec v$

$L$$p\gt0$$q\gt 0$$w$$p$$L$$p$$w$$w$$w=uxyzv$$u$$x$$y$$z$$v$

1. $xz$
2. $xyz$$p$
3. $\hat x$$\hat y$$\hat z$
   1. $\hat x \prec x$$\hat y \prec y$$\hat z \prec z$
   2. $1 \leq \mid \hat x \hat z \mid \leq q$$1 \leq \mid \hat y \mid \leq q$
   3. $ux^j\hat x^i\hat y\hat z^iz^jv$$L$$i \geq 0$$j \geq 0$

$y$$xz$$\hat x\hat z$$\hat y$$q$$x^j$$z^j$$j \geq 0$$j=1$ simplifier la comptabilité lors de l'application du lemme.

$p$$2q$$i = p + 2q$$i = p + q$$\hat z$

$j$$j$$i$$h$$q$$j=i+h$

$d$$[1,q]$$h$$k$$k$$10^j10^j$

.

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

$L$$\qquad\begin{align} S &\to AXBY \mid BYAX \\ A &\to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1 \\ B &\to 1 \mid 0B0 \mid 0B1 \mid 1B0 \mid 1B1 \\ X &\to 0 \mid 0X0 \mid 0X1 \mid 1X0 \mid 1X1 \\ Y &\to 1 \mid 0Y0 \mid 0Y1 \mid 1Y0 \mid 1Y1 \\ \end{align}$