É {

30

É o idioma { } ou não livre de contexto?aibjck | ij,ik,jk

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?

Cem Say
fonte
11
@Sariel: Espero que não seja um problema de lição de casa, porque não sei como resolvê-lo.
Tsuyoshi Ito
3
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.
Cem Say
2
Você pode explicar por que as técnicas padrão não funcionam?
Warren Schudy
3
@Tsuyoshi ... Yeh. Você está certo. É mais difícil do que parece.
Sariel Har-Peled
3
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

Respostas:

28

O lema de Ogden deve funcionar:

Para um dado escolha a i b p c kpaibpck e marque todos os (e nada mais).b

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 aikbb um onde seja igual a k .ik

Ou seja, e k devem ser do conjunto 1 n p { p - n + m n m N 0 } .ik1np{pn+mnmN0}

Tenho certeza, mas com preguiça de provar formalmente que esse conjunto é infinito.

Frank Weinberg
fonte
5
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}.
Tsuyoshi Ito
11
Quem não conhece o lema de Ogden (como eu) pode achar a Wikipedia útil.
Tsuyoshi Ito
2
@Tsuyoshi: Sim, você está certo. Não vi essa representação simples ontem à noite.
Frank Weinberg
11
Esta resposta é apresentada no blog da comunidade .
Aaron Sterling
Uma prova semelhante é apresentada nesta resposta em cs.se.
Hsien-Chih Chang #
-4

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 ki k , j 0 } , L 3 = { a i bL1={aibjckij, k0}L2={aibjckik, j0} (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 ji j } concatenado para { c } .L3={aibjckjk, i0}LiL1{aibjij}{c}

O idioma desejado é a união do anterior . Então, é CFL.L=L1L2L3

R_G
fonte
5
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 } . aabccL1Laabcc{aibjck | ij,ik,jk}
Dave Clarke
4
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).
26411 DaniCL