Como posso provar que essa linguagem não é livre de contexto?

11

Eu tenho o seguinte idioma

{0i1j2k0ijk}

Estou tentando determinar em qual classe de idioma Chomsky se encaixa. Eu posso ver como isso pode ser feito usando uma gramática sensível ao contexto, então eu sei que é pelo menos sensível ao contexto. Parece que não seria possível criar uma gramática livre de contexto, mas estou tendo problemas para provar isso.

Parece para passar o lema de bombagem do garfo porque se é tudo colocado na terceira parte de qualquer palavra (a secção com todos os s). Ele poderia bombear o e tantas vezes quanto você quer e ele iria ficar na língua. Se estou errado, você pode me dizer por que, se estou certo, ainda acho que essa linguagem não é livre de contexto, então como poderia provar isso?uvwxy2vx

justausr
fonte
Não sei como torná-lo uma prova formal, mas garantir que i <= j <= k requer contexto (o valor da variável anterior).
Kevin
@ Rafael, eu li esse post antes deste e não sabia como aplicá-lo ao meu exemplo por causa de sua abstração. Como o relacionamento de cada caractere é> = o número de caracteres anteriores, eu não conseguia ver como dividir o uxyzv na palavra para usar o lema de Ogden. BlueMagister e jmad expandiram no outro post para deixar claro para o meu exemplo.
justausr
@ Rafael Não concordo que esta seja uma aplicação trivial do caso geral. Escolher qual método usar e em qual exemplo aplicá-lo não é tão fácil.
Gilles 'SO- stop being evil'

Respostas:

7

Você pode forçar o bombeamento a estar em alguns lugares, usando o lema de Ogden , por exemplo, marcando todos os 0s.

Suponha que seja livre de contexto, o lema de Ogden fornece um , um que está no idioma e você "marca" todos os 0s. Então qualquer fatoração deve ser tal que exista um em ou . Você também pode assumir e pois e devem ser substrings do seu idioma.p>0w=0p1p2pw=uxyzv0xzx=akz=bmxxzz

  1. Se então tem mais 0 que 1z=0...0w=ux2yz2v

  2. Se e então possui mais 1 que 2.x=0..0z=1..1w=ux2yz2v

  3. Se e então possui mais 0 que 1.x=0..0z=2..2w=ux2yz2v

Portanto, não é uma palavra do seu idioma. Portanto, não é livre de contexto.ux2yz2v

Para outras técnicas, consulte a discussão: Como provar que uma linguagem não é livre de contexto?

jmad
fonte
É para o mesmo idioma que eu tenho? Parece ser para o idioma semelhante em que todos os zeros e zeros são iguais. Este idioma tem o número de 2's> = o número de 1's> = o número de 0's
justausr
1
Sim, mas usando qualquer um dos lemas de bombeamento, você escolhe a palavra (e eu escolhi ): O lema de Ogden deve funcionar para todos eles. 0p1p2p
Jmad
Entendi, nunca ouvi falar do lema de Ogden, então terei que investigá-lo. Eu estava certo ao afirmar que falha no lema de bombeamento?
21712 justausr
@justausr também não, até recentemente (e graças à discussão a que me referi). E sim, você estava certo: o lema de bombeamento faz quase a mesma coisa, mas não escolher onde bombear o torna inútil aqui.
Jmad
5

O lema de bombeamento deve resolver seu problema em relação à terceira parte da palavra; observe que quando você divide , qualquer combinação de também está no idioma, inclusive quando . Tente isso.z=uvwxyuvnwxnyn=0

EDIT: Como jmad afirma , o Lemma Pumping é como um jogo:

  1. O lema de bombeamento fornece ump
  2. Você fornece uma palavra da língua de comprimento pelo menossp
  3. O lema de bombeamento reescreve-o assim: com algumas condições ( e )s=uvxyz|vxy|p|vy|1
  4. Você fornece um número inteiron0
  5. Se não estiver em , você vence, não é livre de contexto.uvnxynzLL

Portanto, o que você precisa fazer é declarar uma palavra, dividir 3 em casos e mostrar que, para cada caso, você pode encontrar um tal que a palavra resultante não esteja no idioma.n

Quando você divide , pense em todos os casos em que o pode se enquadrar. Observe que, se o não se enquadra nos 2, é fácil bombear os 0 e 1 até que superem os 2 e, em seguida, você tem uma palavra que não está no idioma. Minha sugestão é que, se o cair em 2 territórios, você também pode fazer com que e desapareçam definindo , então . Ao eliminar um 2, você pode chegar a uma palavra que não cai no idioma.s=uvxyzvxyvxyvxyvyn=0uvnxynz=uxz

Blue Magister
fonte
Você está dizendo colocar todo o uvwxy na seção com 2's?
justausr
Se for dada a palavra certa. Vou elaborar minha resposta.
Blue Magister
Aqui, tente agora. Não tenho certeza se meu lema de bombeamento é igual ao seu lema de bombeamento, por isso apelo à Wikipedia .
Blue Magister