A linguagem dos pares de palavras de igual comprimento cuja distância de impedimento é 2 ou maior sem contexto?

26

O seguinte contexto de linguagem é livre?

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

Conforme apontado por sdcvvc, uma palavra nesse idioma também pode ser descrita como a concatenação de duas palavras do mesmo comprimento cuja distância de interferência é 2 ou maior.

Eu acho que não é livre de contexto, mas estou tendo dificuldades para provar isso. Tentei cruzar esse idioma com um idioma regular (como por exemplo) e depois use o lema de bombeamento e \ ou homomorfismos, mas sempre recebo um idioma muito complicado para caracterizar e escrever baixa. 0101

Robert777
fonte
Você tentou bombear a corda ? 0u1x1u0x
Gål GD
Sim, mas não consegui extrair essa string do idioma (isso não significa que não é possível, apenas que falhei em fazê-lo).
Robert777
11
@ PålGD, você provavelmente precisa de um caminho para "marcar" as peças, como1u01x01u01x0
vonbrand
8
Esse idioma pode ser escrito como que é a distância de Hamming. Observe que, se substituirmos 2 por 1, ele será livre de contexto ( cs.stackexchange.com/questions/307 ), mas o truque usado não funcionará. Pessoalmente, aposto que não é livre de contexto. {uv:|u|=|v|,d(u,v)2}d
sdcvvc
11
@sdcvvc: Você está certo, uma divide o em modo que um dos bits diferentes esteja em e o outro em . Eu estou corrigido. uuxux
András Salamon

Respostas:

7

Nota [2019-07-30] A prova está errada ... a pergunta é mais complicada do que parece.

Após uma tentativa fracassada aqui, é outra idéia.

Se cruzarmos com o idioma regular , obteremos um idioma CF.LLreg=0101010

Talvez possamos ter mais sorte se usarmos (uma string com exatamente 4 1s).Lreg=010101010

Seja , informalmente se puder ser dividido em duas metades, de modo que a metade contenha exatamente ou ambas as metades contenham s mas suas posições não coincidem.L1=LLregwL1{0,1,3,4} 1s1

Suponha que seja CF e seja sua gramática na forma normal de Chomsky, e deixeL1G

w=uv=0a10b10c10d10eL1

Nós temos(comprimento par)|u|=|v|d(u,v)2

Se restringirmos nossa atenção às maneiras pelas quais os quatro 1s de podem ser gerados, teremos os três casos mostrados na parte superior da figura 1. A parte central da figura 1 mostra o primeiro caso (mas os outros são semelhantes) .w

insira a descrição da imagem aqui
Figura 1 (a imagem completa pode ser baixada aqui )

Se escolhermos e , vemos que os zeros entre os dois pares de 1s devem ser bombeáveis ​​independentemente (nós vermelhos na figura): em particular, para suficientemente grandes , obtemos um nó não terminal duplicado em uma subárvore interna (nó X na figura 2) ou uma subsequência repetida no caminho para o primeiro ou o segundo 1 (nó Y na figura 2). Note-se que a Figura 2 é um pouco simplificado: não pode ser mais nodos não-terminais entre os dois s, e também entre os dois ( , mas com que produz apenas 0s à direita do primeiro 1).a=e,c=2ab,dabaXYsY...Zi...YZi

insira a descrição da imagem aqui
Figura 2

Portanto, podemos corrigir um arbitrário , em seguida, escolher suficientemente grande para obter um nó bombeável independentemente na sequência de zeros entre o primeiro e o segundo . Para a sequência de zeros entre o terceiro e o quarto 1, podemos escolher . Mas é bombeável independentemente, de modo que existe uma substring bombeável , ou seja, tal que e . A string que obtemos é:a=e=k,c=2ab1d=b!+b0 b p b y b = x y z , | y | = p , | x |
0bpbyb=xyz,|y|=p,|x|0,|z|0xyiz=b!+b

w=0k10b!+b102k10b!+b10k

mas . Portanto, não é CF e, finalmente, não é CF.wL1L1L

Se a prova estiver correta (???), ela poderá ser estendida para todos os idiomasLk={uv:|u|=|v|,d(u,v)k},k2

Vor
fonte
Receio que a recompensa expire antes que possamos realmente verificar essa prova. Portanto, a menos que surja alguma informação drástica nas próximas 4 horas, isso indica os pontos por ser a melhor tentativa até agora.
jmite
@jmite: não se preocupe há grandes chances de que é uma tentativa errada como o anterior (que durou cerca de 30 minutos antes de descobrir um erro trivial) :-) :-)
Vor
Por que a distinção entre casos? Os ramos da gramática não têm relação com as metades da palavra. Mas acho que isso não importa; se a prova funcionar, essa distinção entre maiúsculas e minúsculas não é necessária. Observar uma gramática assumida e usar a prova do lema Pumping em vez do lema em si é um bom truque (deve-se fazer isso com mais frequência). Eu tenho uma preocupação (real): se você bombear uma substring de , obtém ; Não vejo como você consegue. Não pense que isso deve prejudicar a prova, mas é melhor verificar. Além disso, convém corrigir algumas notações (e erros de digitação). 0 b + p ( i - 1 )0b0b+p(i1)b+b!
Raphael
11
@ Rafael: obrigado pelos comentários. Talvez eu esteja errado, mas se você escolher como comprimento alvoentão, para cada comprimento de bombeamento , a cadeia pode ser decomposta em e pode ser bombeada para, de fato, no seu exemplo, p certamente divide, então existe um para o qual, mas o comprimento da string original é , portanto, o comprimento total bombeado é. Lembro-me de alguns exercícios que usam o lema de Ogden ... agora vou checá-los. p 0 bb+b!p0bx y i z = b + b ! b ! ( i - 1 1 ) z |0xyz,(|xyz|=b,|y|=pb)xyiz=b+b!b!p ( i - 1 ) = b ! b | x y ( i -(i1)p(i1)=b!b|xy(i1)z|=b+b!
Vor
@ Rafael: ... Eu não encontrei a prova em lugar algum, mas apenas um artigo de Zach Tomaszewski que comprova que o complemento de é CF (veja a pergunta ), então talvez seja uma nova resultado (embora simples); e um teorema do estilo do lema de bombeamento pode ser derivado para idiomas com strings que contêm um número finito de um símbolo específico e substrings de comprimento arbóreo entre eles. Ldup={ww}
Vor
2

Após duas tentativas fracassadas, que foram reprovadas por @Hendrik Jan (obrigado), aqui está outra, que não tem mais sucesso. A @Vor encontrou um exemplo de uma linguagem CF determinística em que a mesma construção seria aplicada, se correta. Isso permitiu identificar um erro na ancoragem da string na aplicação do lema. O próprio lema não parece estar errado. Esta é claramente uma construção simplista demais. Veja mais detalhes nos comentários.y


O idioma não é livre de contexto.L={uxvyu,v,x,y{0,1}{ϵ} , u∣=∣v , uv , x∣=∣y , xy }

É útil ter em mente a caracterização que d é a distância de Hamming, proposta por @sdcvvc. O que é preciso pensar são duas posições selecionadas em cada meia corda, de modo que os símbolos correspondentes sejam diferentes.L={uv:|u|=|v|,d(u,v)2}

Então você considera uma sequência tal que e são pares. É claramente na linguagem L, cortando e em qualquer lugar entre os dois 1 de. Queremos bombear essa corda na primeira parte entre os , para que ela se torne que não deveria estar no idioma. i < j i + j u x 10 j 10 j10i10ji<ji+jux10j10j

Primeiro tentamos usar o lema de Ogden , que é como o lema de bombeamento, mas se aplica a ou mais símbolos distintos marcados na corda, sendo o comprimento de bombeamento para símbolos marcados (mas o lema pode bombear mais porque também pode bombear símbolos não marcados). O comprimento marcado de bombeamento depende apenas do idioma. Essa tentativa falhará, mas a falha será uma dica.p pppp

Podemos então escolher e marcar os símbolos na primeira sequência de . Sabemos que nenhum dos dois 1s estará na bomba, porque ele pode bombear uma vez (expoente 0) em vez de bombear. E bombear os 1s nos tiraria do idioma.ii=pi

No entanto, poderíamos bombear os dois lados do segundo 1 tão rápido ou até mais rápido no lado direito, para que o segundo 1 nunca atravessasse o meio da corda. Além disso, o lema de Ogden não fixa um limite superior ao tamanho do que está sendo bombeado, de modo que não é possível organizar o bombeamento para obter o 1 mais à direita exatamente no meio da corda.

Usamos uma versão modificada do lema, aqui chamada Nash's Lemma, que pode lidar com essas dificuldades.

Primeiro precisamos de uma definição (provavelmente tem outro nome na literatura, mas não sei qual - a ajuda é bem-vinda). Diz-se que uma corda é um apagamento de uma corda se for obtida de apagando símbolos em . Veremos .v v v u vuvvvuv

Lema de Nash: Se é uma linguagem livre de contexto, existem dois números e modo que, para qualquer string de comprimento pelo menos em , e toda forma de “marcar” ou mais de as posições em , podem ser escritas como com a cadeia , , , , , de modo quep > 0 q > 0 w P L p w w w = u x y zLp>0q>0wpLpwwu x y z vw=uxyzvuxyzv

  1. xz tem pelo menos uma posição marcada,
  2. pxyz tem no máximo posições marcadas ep
  3. existem 3 cadeias , , modo que x^ zy^z^
    1. x^x , , , zzy^yz^z
    2. 1 | y | q1≤∣x^z^∣≤q , e1≤∣y^∣≤q
    3. L i 0 j 0uxjx^iy^z^izjv está em para cada e para cada .Li0j0

Prova : semelhante à prova do lema de Ogden, mas as subárvores correspondentes às seqüências e são podadas para que elas não contenham nenhum caminho com o dobro do mesmo não terminal (exceto as raízes dessas duas subárvores). Isso necessariamente limita o tamanho das cadeias geradas e por uma constante . As cadeias e , para , correspondentes a uma versão não podada da árvore, são usadas principalmente com para simplificar a contabilidade quando o lema é aplicado.x z x z y Q x J z j j 0 j = 1yxzx^z^y^qxjzjj0j=1

Modificamos a tentativa de prova acima, marcando símbolos mais à esquerda 0, mas eles são seguidos por símbolos 0 para garantir que bombeemos na parte esquerda da string, entre os dois 1s. Isso totaliza 0's entre os (na verdade seria suficiente, pois o 1 mais à direita não pode estar em , o que permitiria removê-lo simplesmente).2 q i = p + 2 q i = p + q zp2qi=p+2qi=p+qz^

O que resta é ter escolhido para que possamos bombear exatamente o número certo de zeros para que as duas sequências sejam iguais. Mas até agora, a única restrição em j é ser maior que i . E também sabemos que o número de 0s que são bombeados em cada bombeamento está entre 1 e q. Então, seja h produto dos primeiros q inteiros. Nós escolhemos j = i + h .jjihqj=i+h

Portanto, como o incremento de bombeamento - seja o que for - está em [ 1 , q ] , ele divide h . Seja k o quociente. Se bombearmos exatamente k vezes, obteremos uma sequência 10 j 10 j que não está no idioma. Portanto, L não é livre de contexto.d[1,q]hkk10j10j

.

Eu acho que nunca verei
Uma corda adorável como uma árvore.
Pois, se não tiver uma análise,
A corda é apenas uma farsa

babou
fonte
Note, no entanto, que o passe na segunda metade lê a pilha ao contrário. Isso parece significar que as duas posições estão na mesma posição nas duas metades, mas ao contrário?
Hendrik Jan
você está correto ... eu brinquei ... agora eu sei o que estava me incomodando na parte de trás da minha cabeça.
babou
Reconheci o argumento (porque não consegui fazê-lo funcionar quando me tentei).
Hendrik Jan
aibjckaibjck
@HendrikJan Eu brinquei de novo? (BTW, obrigado por tornando-se uma discussão)
babou
-1

LSAXBYBYAXA00A00A11A01A1B10B00B11B01B1X00X00X11X01X1Y10Y00Y11Y01Y1

MK Dadsetani
fonte
4
Isso está incorreto; você não pode garantir que o comprimento do AX seja o mesmo que BY. Por exemplo, sua gramática gera S -> AXBY -> A011 -> 0A1011 -> 001011, que não está no idioma original. Além disso, seus símbolos A e X geram o mesmo idioma, o mesmo para B e Y; eles podem ser mesclados.
sdcvvc