Cómo demostrar que el lenguaje definido como [matemáticas] L = \ {a ^ {n + 1} b ^ n: n \ ge 0 \} [/ matemáticas] no es regular utilizando el lema de bombeo (informática)

La propiedad hinchada? ¿Es ese otro nombre para el lema de bombeo?

Supongamos, en aras de la contradicción, que el lenguaje dado es regular, que es reconocido por algún autómata finito determinista con … digamos [matemáticas] p [/ matemáticas] estados. Como [math] a ^ {p + 1} b ^ p \ en L [/ math], se deduce que en la entrada [math] a ^ {p + 1} b ^ p [/ math], el DFA se mueve desde estado inicial a un estado de aceptación. Pero según el Principio de Pigeonhole, antes de que termine de procesar los [math] a [/ math] ‘s, debe visitar algún estado en particular al menos dos veces. Por lo tanto, podemos dividir la cadena [matemática] a ^ {p + 1} b ^ p [/ matemática] en tres partes, [matemática] x [/ matemática], [matemática] y [/ matemática] y [matemática] z [/ math], donde [math] x [/ math] es la parte que nos lleva al primer estado repetido; [math] y [/ math] es la cadena no vacía más corta que nos lleva del estado repetido a sí mismo, y [math] z [/ math] es el resto de la cadena después de la repetición del primer estado.

Formalmente:

• [matemáticas] a ^ {p + 1} b ^ p = xyz [/ matemáticas];
• [matemáticas] | xy | \ leq p [/ matemáticas];
• [matemáticas] | y |> 0 [/ matemáticas].

Dado que la cadena [math] xyz [/ math] es aceptada por el DFA y la subcadena [math] y [/ math] tiene los mismos estados de inicio y fin, podemos repetir esta subcadena tantas veces como queramos (o no en todas). Es decir, para cualquier [matemática] k \ geq 0 [/ matemática], [matemática] xy ^ kz \ en L [/ matemática]. Por supuesto, [math] xy [/ math] es una subcadena de [math] a ^ {p + 1} [/ math] debido a su longitud, por lo que [math] x [/ math] es una subcadena más corta. Esto significa que [math] xz \ en L [/ math], y sin embargo, se obtiene de un miembro de [math] L [/ math] eliminando algunos [math] a [/ math] ‘s y no [math] b [/ math] ‘s. Formalmente, [matemáticas] xz = a ^ {p + 1- | y |} b ^ p \ notin L [/ matemáticas].

En otras palabras, este DFA (y, en consecuencia, cualquier DFA que acepte todas las palabras de [math] L [/ math]) necesariamente debe aceptar al menos una palabra que no esté en [math] L [/ math]. Esta contradicción muestra que [matemáticas] L [/ matemáticas] no es, de hecho, un lenguaje regular.