Aplicación del lema de idiomas regulares de bombeo

Question

Necesito a prueba mediante el Bombeo lema de que el lenguaje $L = \{0^m1^n \;|\; m \geq n\}$ no es regular.

De acuerdo con el lema de Bombeo para cada lenguaje regular una palabra $w = xyz$ existe, que $$\forall n,k \in \mathbb{N} \text{ with } 0 < |y| \leq |xy| \leq n$$ applies: $$xy^kz \in L$$

No estoy seguro de cómo construir la palabra w. Esto es lo que he intentado:

$$w = 0^n1^{n-1}, x = \lambda, y = 0^n \Rightarrow |xy| = n \leq n$$ (condición de Bombeo lema).

Si I k a $0$ I get $$w = xy^0z = xz = \lambda z = z = 1^{n-1} \not\in L$$ because $$|_1w| = n-1 > |_0w| = 0 $$ $\Rightarrow L $ ist no regular.

La única restricción para mi es la prueba de $k > 0$.

Esto es correcto? Gracias de antemano!

Answer 1

Pensar en el Lema de Bombeo como un juego en el que usted está tratando de demostrar que un lenguaje no es regular, mientras que otra persona está "defendiendo" la regularidad de este idioma. Aquí es cómo jugar el juego:

1. El defensor especifica la longitud de bombeo $n$. Piense en ello como el número de estados del autómata que reconoce el idioma.
2. Dar el defensor de una palabra $w$ desde el lenguaje, que satisface la condición: $|w| \ge n$.
3. El defensor divide esta palabra en $xyz$ donde$|xy| \le n$$|y| > 0$. Esta división también debe satisfacer la condición de que $xy^{k}z$ pertenece a la lengua $\forall k \ge 0$.

Si usted le da al defensor de una palabra que es imposible dividir en las condiciones que en el paso 3, usted gana y el lenguaje no es regular.

---

Teniendo en cuenta lo anterior, vamos a echar un vistazo a su respuesta. Usted le dio a la palabra $0^{n}1^{n-1}$. Voy a jugar el papel de defensor y se divide como: $0^{n-1}01^{n-1}$ donde $x = 0^{n-1}$, $y = 0$ y $z = 1^{n-1}$. Esta división satisfaga todas las condiciones anteriores:

• $|xy| = |0^n| \le n$
• $|y| = |0| = 1 \ge 0$
• $xy^{k}z = 0^{n-1}0^{k}1^{n-1} = 0^{n+k-1}1^{n-1} \in L$

La última condición se justifica porque:

$$ k \ge 0 \Rightarrow n+k-1 \ge n-1 $$

Por lo tanto, su palabra no hacer que sea imposible para mí para dividir la palabra en una forma que cumple el Lema de Bombeo.

Ahora, lo que si tenemos en cuenta $0^{n}1^{n}$ lugar? No importa cómo puedo dividir, $x$ $y$ siempre entran dentro de la $0^n$ desde $|xy| \le n$. Por lo tanto, $y$ constará de uno o más $0$s. Para $k = 0$, uno o más $0$s será eliminado y el número de $0$s en la cadena ser menor que el número de $1$s, y la palabra ya no será en el idioma. Por lo tanto, el lenguaje no es regular.

Answer 2

Eso no es cierto. Pensar en el lema de bombeo como un juego:

• El señor de Bombeo Lema le da una constante $n$.
• Elige una palabra $w$ en el idioma de la longitud de, al menos,$n$.
• El señor de Bombeo Lema le da $x$, $y$, y $z$ con $xyz=w$, $|xy|≤n$, y $y$ no está vacío.
• Ahora que usted escoja $r$.
• El señor de Bombeo Lema afirma que $xy^rz$ es también en el lenguaje.
• Si se equivoca, usted gana.

En su pregunta, parece que una vez que usted escogió $w$, le siguió adelante y se eligió $x$$y$. Usted no puede hacer esto. Ese es el Lema de Bombeo del trabajo.

Puede corregir la prueba? No en el paso 3, por desgracia. Si el Señor de Bombeo Lema recoge $x={\tt 0}^{n-1}$$y={\tt 0}$$z={\tt 1}^{n-1}$, le siguieron las reglas. Pero incluso si usted escoge $r=0$ en el paso 4, no funciona: el Señor de Bombeo Lema afirma en el paso 5 $xy^0z = {\tt 0}^{n-1}{\tt 1}^{n-1}$ es todavía en la lengua, y él está a la derecha. Y si tienes que elegir un mayor $r$ en el paso 4, es incluso peor para usted.

Pero usted puede arreglar su prueba. Usted necesita para hacer de $w$ un poco diferente en el paso 2. Tratar de fijación de modo que cuando se eliminan $y$ al final, la parte con la ${\tt 0}$s'es demasiado corto.

Answer 3

Considerar prueba inversa de lengua L para ser no-regular. Su fácil de hacer. Entonces usando la propiedad de cierre de idiomas regulares (inversa de un lenguaje regular es regular) dicen que desde que Reverse(L) no es regular por lo tanto L no se puede regular así.