Depois de ler a pergunta recente "O complemento de livre de contexto?" ; Lembrei-me de um problema semelhante que não era capaz de refutar:
É livre de contexto?
Aqui exigimos que as duas cordas sejam diferentes em pelo menos duas posições (a distância de Hamming deve ser maior que ).
É livre de contexto se que (ou seja, as duas cadeias simplesmente devam ser diferentes).
Suspeito que a linguagem não seja livre de contexto: se a interceptarmos com o normal , obtemos casos em que um PDA deve "lembrar" duas posições na ordem inversa após atingir a metade da corda.
Atualização: se cruzarmos com o , obteremos uma linguagem livre de contexto, como mostra domotorp em sua resposta; um um pouco mais complexo com (mais um para "acompanhar") ainda sugere que não deve ser livre de contexto.
fonte
Respostas:
A interseção com length length words é livre de contexto, porque um PDA pode se lembrar de duas posições, de certa forma. De qualquer forma, vamos primeiro ver o que esta linguagem é. Seu complemento é . Portanto, . Podemos reescrever isso como .R = { 0∗10∗10∗10∗∣ } L R ∖ L = { 0 a 10 b 10 c 10 d | b = n / 2 ∨ c = n / 2 ∨ um + d = n / 2 } L = { 0 a 10 b 10 c 10 d ∣eu R ∖ L = { 0uma10b10c10d∣ b = n / 2 ∨ c = n / 2 ∨ a + d= n / 2 } L = { 0uma10b10c10d∣b≠n/2∧c≠n/2∧a+d≠n/2} L={0a10b10c10d∣b>n/2∨c>n/2∨a+d>n/2∨b,c,a+d<n/2}
Os primeiros casos podem ser facilmente verificados e o quarto.3
fonte