Este idioma é livre de contexto?

8

É o idioma

L={a,b}{(anbn)nn1}

sem contexto? Acredito que a resposta é que não é uma CFL, mas não posso provar pelo lema de Ogden ou Pumping.

Andrés Felipe Téllez Crespo
fonte
Crossposted em math.SE ; por favor não faça isso! Você checou a pergunta que eu te indiquei? Inclua suas tentativas e por que elas falham.
Raphael
O teorema de Parikh funciona para mas não para ; infelizmente, . Até o lema Interchange parece estar cumprido. Uau, desagradável. {(anbn)nn1}LΨ{a,b}[L]=N2
Raphael

Respostas:

8

Dica:

sim

Solução:

{(anbn)nn1}={an1bn2an2k1bn2k}:k1n1=ki.ni=ni+1}


e, portanto, o complemento é que é livre de contexto, pois você pode escrever facilmente um PDA não determinístico.

{a,b}{(anbn)nn1}={an1bn2an2k1bn2k:n1ki.nini+1}


sdcvvc
fonte
2
Ooohhh! * facepalm * Talvez você queira adicionar o truque central de design; pode não ser óbvio para o novato.
Raphael
Não entendo, pensei que o complemento de uma CFL não fosse a CFL em geral. Obrigado
Andrés Felipe Téllez Crespo
{(anbn)n} não é livre de contexto, mas seu complemento é.
Sdcvvc
@ AndrésFelipeTéllezCrespo: O complemento de uma CFL nem sempre é CFL (portanto, nenhuma propriedade de fechamento), mas ninguém diz que não há CFL cujo complemento é CFL. Em particular, todos os complementos de todas as linguagens regulares são livres de contexto (porque são regulares).
Raphael
Idiomas semelhantes a - uma disjunção finita de condições adequadas - podem ser resolvidos usando o não-determinismo: adivinhe a condição violada e verifique se ela é violada (ignore o resto). L
Raphael