É o idioma { } ou não livre de contexto?aibjck | i≠j,i≠k,j≠kaibjck | i≠j,i≠k,j≠k
Percebi que encontrei quase todas as variantes dessa questão com diferentes condições sobre a relação entre i, j e k, mas não essa.
Meu palpite é que não é livre de contexto, mas você tem uma prova?
@Sariel: Espero que não seja um problema de lição de casa, porque não sei como resolvê-lo.
Parece um problema de lição de casa, pois algumas das outras variantes mencionadas são suficientemente fáceis para serem problemas de lição de casa. Mas essa variante não é um problema de lição de casa. Eu ficaria feliz se alguém pudesse me fornecer um link para qualquer site do curso em que esse problema específico tenha sido atribuído como tarefa de casa.
Você pode explicar por que as técnicas padrão não funcionam?
@Tsuyoshi ... Yeh. Você está certo. É mais difícil do que parece.
Curiosamente, essa linguagem (e o uso do Lema de Ogden) pode ser encontrada no Exemplo 6.3 (p. 130) na versão clássica de "Introdução à Teoria dos Autômatos, Idiomas e Computação" de Hopcroft e Ullman.
— Dominik D. Freydenberger
O lema de Ogden deve funcionar:
Para um dado escolha a i b p c kppaibpckaibpck e marque todos os (e nada mais).bb
e k são escolhidos de tal forma que, para cada escolha de quantos b 's são realmente bombeados, existe um expoente de bombeamento tal que o número de b ' s seja igual aiikkbbbb um onde seja igual a k .iikk
Ou seja, e k devem ser do conjunto ⋂ 1 ≤ n ≤ p { p - n + m ∗ n ∣ m ∈ N 0 } .iikk⋂1≤n≤p{p−n+m∗n∣m∈N0}⋂1≤n≤p{p−n+m∗n∣m∈N0}
Tenho certeza, mas com preguiça de provar formalmente que esse conjunto é infinito.
— Frank Weinberg
Supondo que IN_0 signifique o conjunto de números inteiros não negativos, o conjunto mencionado é infinito porque contém p + im para i = 0, 1, 2,…, onde m é o múltiplo menos comum de {1,…, p}.
Quem não conhece o lema de Ogden (como eu) pode achar a Wikipedia útil.
@Tsuyoshi: Sim, você está certo. Não vi essa representação simples ontem à noite.
Esta resposta é apresentada no blog da comunidade .
Uma prova semelhante é apresentada nesta resposta em cs.se.
— Hsien-Chih Chang #
Se a relação entre as três restrições for "OR", o idioma será CFL. A solução usa o fato de que as CFLs estão fechadas em união. Claramente, os seguintes são CFLs: , L 2 = { a i b j c k ∣ i ≠ k , j ≥ 0 } , L 3 = { a i bL1={aibjck∣i≠j, k≥0}L1={aibjck∣i≠j, k≥0}L2={aibjck∣i≠k, j≥0}L2={aibjck∣i≠k, j≥0} (se não se convencer, pode-se considerar L i como concatenação de CFL e linguagem regular. Por exemplo, L 1 é { a i b j ∣ i ≠ j } concatenado para { c } ∗ .L3={aibjck∣j≠k, i≥0}L3={aibjck∣j≠k, i≥0}LiLiL1L1{aibj∣i≠j}{aibj∣i≠j}{c}∗{c}∗
O idioma desejado é a união do anterior . Então, é CFL.L=L1∪L2∪L3L=L1∪L2∪L3
— R_G
Isto está errado. Por exemplo, e, portanto, em seu L , mas a a b c c ∉ { a i b j c k | i ≠ j , i ≠ k , j ≠ k } . aabcc∈L1aabcc∈L1LLaabcc∉{aibjck | i≠j,i≠k,j≠k}aabcc∉{aibjck | i≠j,i≠k,j≠k}
Você assume que »a relação entre as três restrições é" OR "«, mas esse não é o significado pretendido. Todas as restrições precisam ser mantidas (consulte o contra-exemplo de Dave Clarke) e, em seguida, o idioma não será livre de contexto (consulte a resposta acima).