Demostrar que los siguientes lenguajes no son regulares:
c) {0^n10^n|n>=1}
(Traducido desde http://infolab.stanford.edu/~ullman/ialcsols/sol4.html)
Sea n la constante del lema del bombeo (observe que esta n no es la misma n que aparece como variable local en la defnición del lenguaje L arriba. NT: Es decir, podemos llamarla de otra manera). Sea w = 0^n10^n. Entonces, cuando escribamos w = xyz, sabremos que |xy| <= n, y por tanto, y consiste únicamente de 0's (ceros). Así, xz, que debe pertenecer a L si L es regular, consistirá de menos ceros que n, seguidos de por un 1 y exactamente n ceros. (NT Esto supone que y es una cadena formada con alguna porción de la primer subcadena de ceros de w, siempre que no sea vacía. También podría ser otra subcadena, incluso con el uno. El argumento sería similar). Pero esta cadena, xz, no está en L, lo que contradice la suposición de que L es regular. Fin de la prueba.
(fin de la traducción libre).
Ahora intentemos la misma demostración, jugando el juego en
http://jacinto-davila.blogspot.com/2012/01/teocomp-b2011-el-lema-del-bombeo-como.html
1) Sea L = {0^m10^m | m > 0 }
2) Sea w = 0^n10^n, con n>1, xy=0^p1 diferente de lambda.
1) Sea x = 0^i ; y = 0^(n-i) ; z = 10^n con i >= 1 e i < n. Como n > 2, y no es lambda y |xy| = |0^i0^(n-i)| < n
2) bombea diciendo que xy^kz no pertenece a L para k = 0. Es decir, queda claro que |xz| = 0^i10^n con i < n no pertenece al lenguaje. LQQD.
Será más claro así?
c) {0^n10^n|n>=1}
(Traducido desde http://infolab.stanford.edu/~ullman/ialcsols/sol4.html)
Sea n la constante del lema del bombeo (observe que esta n no es la misma n que aparece como variable local en la defnición del lenguaje L arriba. NT: Es decir, podemos llamarla de otra manera). Sea w = 0^n10^n. Entonces, cuando escribamos w = xyz, sabremos que |xy| <= n, y por tanto, y consiste únicamente de 0's (ceros). Así, xz, que debe pertenecer a L si L es regular, consistirá de menos ceros que n, seguidos de por un 1 y exactamente n ceros. (NT Esto supone que y es una cadena formada con alguna porción de la primer subcadena de ceros de w, siempre que no sea vacía. También podría ser otra subcadena, incluso con el uno. El argumento sería similar). Pero esta cadena, xz, no está en L, lo que contradice la suposición de que L es regular. Fin de la prueba.
(fin de la traducción libre).
Ahora intentemos la misma demostración, jugando el juego en
http://jacinto-davila.blogspot.com/2012/01/teocomp-b2011-el-lema-del-bombeo-como.html
1) Sea L = {0^m10^m | m > 0 }
2) Sea w = 0^n10^n, con n>1, xy=0^p1 diferente de lambda.
1) Sea x = 0^i ; y = 0^(n-i) ; z = 10^n con i >= 1 e i < n. Como n > 2, y no es lambda y |xy| = |0^i0^(n-i)| < n
2) bombea diciendo que xy^kz no pertenece a L para k = 0. Es decir, queda claro que |xz| = 0^i10^n con i < n no pertenece al lenguaje. LQQD.
Será más claro así?
0 comentarios:
Publicar un comentario