Cuando se aplica el lema del bombeo a un lenguaje que sí es regular "el adversario gana" y no puede completar la demostración. Mostrar qué es lo que sale mal cuando L es el descrito por esta expresión regular
1) [Para todo L..] Sea L descrito por 01^*0^*1
2) [Existe n.. ] Sea n la constante requerida por el lema.
1) [Para todo w...] Sea w = 01^i0^j1, |w| > n, para algunos i j.
2) [Existen x, y, z...] Sea x=0, y=1^i0^j, z= 1. Claramente y no es vacía y |xy| es menor que n
1) [Para todo k...] No importa el valor de k que escoja, xy^kz pertenece a L. Pues 01^(i*k)0^(j*k)1 representa a cualquier cadena del lenguaje (pues i y j son valores cualesquiera, siempre que aquella |w| sea mayor que n). Esto significa que 1), "el oponente" no puede completar la prueba de que este lenguaje no es regular.
0 comentarios:
Publicar un comentario