¿Cómo puedo demostrar que este lenguaje no está libre de contexto?

Tengo el siguiente idioma

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

Estoy tratando de determinar en qué clase de idioma Chomsky encaja. Puedo ver cómo se podría hacer usando una gramática sensible al contexto, así que sé que al menos es sensible al contexto. Parece que no sería posible hacerlo con una gramática libre de contexto, pero tengo un problema para demostrarlo.

Parece pasar el lema de bombeo de horquilla porque si se coloca en la tercera parte de cualquier palabra (la sección con todos los s). Podría bombear y tantas veces como desee y permanecería en el idioma. Si me equivoco, ¿podría decirme por qué, si estoy en lo cierto, sigo pensando que este lenguaje no está libre de contexto, entonces, ¿cómo podría probarlo?2 v $uvwxy$$2$$v$$x$

Puede forzar el bombeo en algunos lugares, utilizando el lema de Ogden , por ejemplo, marcando todos los 0.

Supongamos que está libre de contexto, luego el lema de Ogden le da un , le da que está en el lenguaje y "marca" todos los 0. Entonces cualquier factorización debe ser tal que haya un en o . También puede suponer y ya que y deben ser subcadenas de su idioma.w = 0 p 1 p 2 p w = u x y z v 0 x z x = a k z = b m x x z $p>0$$w=0^p1^p2^p$$w=uxyzv$$0$$x$$z$$x=a^k$$z=b^m$$xx$$zz$

1. Si entonces tiene más 0 que 1w = u x 2 y z 2$z=0...0$$w=ux^2yz^2v$

2. Si y entonces tiene más de 1 que de 2.z = 1..1 w = u x 2 y z 2$x=0..0$$z=1..1$$w=ux^2yz^2v$

3. Si y entonces tiene más 0 que 1.z = 2..2 w = u x 2 y z 2$x=0..0$$z=2..2$$w=ux^2yz^2v$

Entonces no es una palabra de tu idioma. Por lo tanto, no está libre de contexto.$ux^2yz^2v$

Para otras técnicas, vea la discusión: ¿Cómo demostrar que un lenguaje no está libre de contexto?

El lema de bombeo debería resolver su problema con respecto a la tercera parte de la palabra; tenga en cuenta que cuando divide , cualquier combinación de también está en el lenguaje, incluso cuando . Trata eso.u v n w x n y n = $z = uvwxy$$uv^nwx^ny$$n = 0$

EDITAR: como dice jmad , Pumping Lemma es como un juego:

1. El lema de bombeo te da una$p$
2. Usted da una palabra del lenguaje de longitud al menos$s$$p$
3. El lema de bombeo lo reescribe así: con algunas condiciones ( y )| v x y | ≤ p | v y | ≥ $s=uvxyz$$|vxy|≤p$$|vy|≥1$
4. Usted da un número entero$n≥0$
5. Si no está en , usted gana, no está libre de contexto.L $uv^nxy^nz$$L$$L$

Entonces, lo que debe hacer es decir una palabra, dividir 3 en casos y mostrar que para cada caso puede encontrar un tal que la palabra resultante no esté en el idioma.$n$

Cuando , piensa en todos los casos en los que puede caer. Usted nota que si no cae en los 2, entonces es fácil bombear los 0 y 1 hasta que superen en número a los 2, y entonces tiene una palabra que no está en el idioma. Mi sugerencia es que, si cae en 2 territorios, también puede hacer que e desaparezcan estableciendo , entonces . Luego, al eliminar un 2, puede llegar a una palabra que no cae en el idioma.v x y v x y v x y v y n = 0 u v n x y n z = u x $s=uvxyz$$vxy$$vxy$$vxy$$v$$y$$n=0$$uv^nxy^nz = uxz$