TeoComp B2011: El lema del bombeo como un juego entre adversarios

El lema del bombeo como un juego entre adversarios
(basado en texto con el mismo nombre que aparece en [1])

Un teorema cuyo enunciado contiene varias alternativas de cuantificadores universales y existenciales puede considerarse un juego entre dos jugadores.

El lema del bombeo se puede plantear así: Para todo lenguaje regular L, existe un n tal que para toda palabra w perteneciente a L, con |w|>=n, existen x, y y z , tales que w=xyz, de modo que y no es la cadena vacía lambda o épsilon  y |xy| <= n, con quienes se cumple que para todo k>=0, la cadena xy^kz también pertenece a L.

Jugador 1: Elige en lenguaje L que pretende demostrar NO es regular.
Jugador 2: Escoge n (sin decir su valor al Jugador 1, quien debería poder sobrevivir a cualquier valor de n).
Jugador 1: Elige w, que puede depender de n y que, en todo caso, debe ser tal que |w|>=n
Jugador 2: Divide a w en  x, y y z , cuidando que  yno sea la cadena vacía y que |xy|<=n
Jugador 1: Gana (es decir, demuestra que L no es regular) si logra encontrar un valor para k, tal que xy^kz no pertenezca a L.


[1] Hopcroft, J. E.;  Motwani, R.; Ullman, J. Introducción a la Teoría de Autómatas, Lenguajes y Computación. Segunda Edición. Pearson Educación. 2002