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

Eu tenho o seguinte idioma

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

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?$uvwxy$$2$$v$$x$

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>0$$w=0^p1^p2^p$$w=uxyzv$$0$$x$$z$$x=a^k$$z=b^m$$xx$$zz$

1. Se então tem mais 0 que 1$z=0...0$$w=ux^2yz^2v$

2. Se e então possui mais 1 que 2.$x=0..0$$z=1..1$$w=ux^2yz^2v$

3. Se e então possui mais 0 que 1.$x=0..0$$z=2..2$$w=ux^2yz^2v$

Portanto, não é uma palavra do seu idioma. Portanto, não é livre de contexto.$ux^2yz^2v$

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

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 = uvwxy$$uv^nwx^ny$$n = 0$

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

1. O lema de bombeamento fornece um$p$
2. Você fornece uma palavra da língua de comprimento pelo menos$s$$p$
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 inteiro$n≥0$
5. Se não estiver em , você vence, não é livre de contexto.$uv^nxy^nz$$L$$L$

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=uvxyz$$vxy$$vxy$$vxy$$v$$y$$n=0$$uv^nxy^nz = uxz$