Entender el lema bombeo

Question

He tenido una muy difícil demostrar que un lenguaje es irregular usando el lema de bombeo. Yo la miré y docenas de ejemplos y pasé horas y horas sobre este tema, y todavía no estoy capaz de envolver mi cabeza alrededor de ella. A continuación es mi primer ejemplo que he trabajado fuera de mi entendimiento hasta este punto. Yo en verdad agradecería si alguien espera en si estoy o no estoy en el camino correcto, y posiblemente lo que puedo hacer para hacer la prueba más fuerte.

O Una somera explicación del lema de Bombeo también será muy apreciada.

Muchas gracias de antemano!

$$L = \{0^{(n)}1^{(n)}2^{(n)}\}$$

Deje $s = 0^{(p)}1^{(p)}2^{(p)}$ donde $|s| > p$.

Considere la posibilidad de $$x=0^i, i >=0$$ $$y=0^j, j >=0$$ $$z=0^{(p-i-j)}1^{(p)}2^{(p)}$$

Considere la posibilidad de $xy^2z$

$$=0^{(p-i-2j)}0^{(j)}0^{(i)}1^{(p)}2^{(p)}$$

$$=0^{(p+j)}1^{(p)}2^{(p)}$$

Ya, $p+j \neq p$

$$0^{(n)}1^{(n)}2^{(n)} \not\in L$$

Answer 1

Cada vez que un personaje se consume, una transición de un estado a otro. Digamos que el DFA tiene 5 estados. La cadena más larga esto puede aceptar sin visitar ningún estado más de una vez es de 4 caracteres de largo. Así que digamos que usted tiene una cadena que es más que eso, de 5 caracteres, por ejemplo, y los estados de la DFA visitas (en este orden) son $s_0, s_1, s_2, s_3, s_4, s_1$. La parte de la cadena coincidente entre el repetido $s_1$ estados puede ser repetido (bombeado) porque cualquiera que sea el carácter de la DFA vio cuando estaba en el $s_1$ el primer tiempo será visto de nuevo la próxima vez que esté en $s_1$, así que voy a repetir la transición. Y así sucesivamente para las demás transiciones de$s_2$$s_3$, etc.

Answer 2

Bombeo lema: Si una lengua $L$ es regular, entonces existe un 'loop' tamaño constante $p\ $ de manera tal que cualquier palabra de más de $p\ $ tiene una granulometría parte en el medio.

El lenguaje es regular = puede ser decidido por un estado de autómatas, y la constante$p$, proviene de un(ny) en particular autómatas, como se describe en el comentario. El 'bombeables parte" en el medio corresponde a los bucles, por supuesto. En las fórmulas, si $x\in L,\ |x|>p$, $x$ puede ser escrito como $x=uvw$ algunos $|v|\ge 1$, e $u(v)^kw\in L$ todos los $k=1,2,3,\dots$

Para el idioma $L_1=\{0^n1^n2^n \mid n\in\Bbb N\}$ por encima de, si era regular, considere la posibilidad de cualquier $n$ tal que $3n>p$, entonces la palabra $x=0^n1^n2^n$ podría ser escrito como $uvw$, pero no se garantiza que las fronteras de $u,v,w$ se ajuste a las fronteras de $0$'s y $1$'s y $2$'s.

Así, usted debe considerar algunas posibilidades de acuerdo a la longitud de $u$$w$. Por ejemplo, $v$ puede ser contenida totalmente en uno de los $0^n$, $1^n$ o $2^n$ bloques, o $v$ pueden cruzar la $0$ $1$- bloques, se $v=0^a1^b$ o, $v=1^b2^c$, o, finalmente,$v=0^a1^n2^b$.

En cualquier caso, ya $uvvw\notin L$.