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

O seguinte contexto de linguagem é livre?

L = {u x v y ∣ u, v, x, y \in {0, 1}^{+}, | u | = | v |, u \neq v, | x | = | y |, x \neq y}

$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\}$

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

formal-languages context-free pushdown-automata pumping-lemma open-problem Robert777
fonte

Você tentou bombear a corda ?

0^{u} 1^{x} 1^{u} 0^{x}

$0^u1^x1^u0^x$

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

@ PålGD, você provavelmente precisa de um caminho para "marcar" as peças, como

1^{u} 0 1^{x} 0 1^{u} 0 1^{x} 0

$1^u 0 1^x 0 1^u 0 1^x 0$

vonbrand

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.

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

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

d

$d$

sdcvvc

@sdcvvc: Você está certo, uma divide o em modo que um dos bits diferentes esteja em e o outro em . Eu estou corrigido.

u

$u$

u^{'} x

$u'x$

u^{'}

$u'$

x

$x$

András Salamon

Respostas:

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

Talvez possamos ter mais sorte se usarmos (uma string com exatamente 4 1s). $L_{reg}' = 0^*10^*10^*10^*10^*$

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

Suponha que seja CF e seja sua gramática na forma normal de Chomsky, e deixe $L_1$ $G$

w = u v = 0^{a} 1 0^{b} 1 0^{c} 1 0^{d} 1 0^{e} \in L_{1}

$w = uv = 0^a 1 0^b 1 0^c 1 0^d 1 0^e \in L_1$

Nós temos(comprimento par) $|u|=|v|$ $d(u,v) \geq 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=2a$ $b,d \gg a$ $b \gg a$ $X$ $Ys$ $Y\to ... \to Z_i \to ... Y$ $Z_i$

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 = 2a$ $b$ $1$ $d = b! +b$
$0^b$ $p \leq b$ $y$ $b = xyz, |y|=p, |x|\geq 0, |z|\geq 0$ $xy^iz = b!+b$

w^{'} = 0^{k} 1 0^{b! + b} 1 0^{2 k} 1 0^{b! + b} 1 0^{k}

$w' = 0^k 1 0^{b!+b} 1 0^{2k} 1 0^{b!+b} 1 0^k$

mas . Portanto, não é CF e, finalmente, não é CF. $w' \notin L_1$ $L_1$ $L$

Se a prova estiver correta (???), ela poderá ser estendida para todos os idiomas $L_k = \{ uv : |u|=|v|, d(u,v)\geq k\}, k\geq 2$

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}

$0^b$

0^{b + p (i - 1)}

$0^{b+p(i-1)}$

b + b!

$b+b!$

Raphael

@ 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.

b + b!

$b+b!$

p

$p$

0^{b}

$0^b$

0^{x y z}, (| x y z | = b, | y | = p \leq b)

$0^{xyz}, (|xyz|=b, |y|=p \leq b)$

x y^{i} z = b + b!

$xy^iz = b + b!$

b!

$b!$

(i - 1)

$(i-1)$

p (i - 1) = b!

$p(i-1)=b!$

b

$b$

| x y^{(i - 1)} z | = b + b!

$|xy^{(i-1)}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.

L_{d u p} = {w w}

$L_{dup} = \{ ww \}$

Vor

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 = \{ 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 \ \}$

É ú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) \geq 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. $10^i10^j$ $i \lt j$ $i+j$ $u$ $x$ $10^j10^j$

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$ $p$ $p$

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. $i=p$ $i$

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 . $u$ $v$ $v$ $v$ $u \prec v$

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 que $L$ $p\gt0$ $q\gt 0$ $w$ $p$ $L$ $p$ $w$ $w$ $w=uxyzv$ $u$ $x$ $y$ $z$ $v$

$xz$ tem pelo menos uma posição marcada,
$xyz$ tem no máximo posições marcadas e $p$
existem 3 cadeias , , modo que 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$ , e $1 \leq \mid \hat y \mid \leq q$
3. $ux^j\hat x^i\hat y\hat z^iz^jv$ está em para cada e para cada . $L$ $i \geq 0$ $j \geq 0$

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. $y$ $xz$ $\hat x\hat z$ $\hat y$ $q$ $x^j$ $z^j$ $j \geq 0$ $j=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). $p$ $2q$ $i = p + 2q$ $i = p + q$ $\hat z$

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 é ser maior que . 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 produto dos primeiros inteiros. Nós escolhemos . $j$ $j$ $i$ $h$ $q$ $j=i+h$

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

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

a^{i} b^{j} c^{k} a^{i} b^{j} c^{k}

${a^ib^jc^ka^ib^jc^k}$

@HendrikJan Eu brinquei de novo? (BTW, obrigado por tornando-se uma discussão)

babou

-1

$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}$

MK Dadsetani
fonte

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