Traducido desde http://infolab.stanford.edu/~ullman/ialcsols/sol4.html
fin de la traducción.
¿Cómo se podría caracterizar esa limitación en términos de memoria?
Sea n la constante del lema del bombeo y sea w = 0^(n^2), es decir, n^2 ceros. Cuando decimos w = xyz sabemos que y consiste de entre 1 y n ceros. Así que xyyz tiene una longitud de entre n^2 + 1 y n^2 + n. Dado que el siguiente cuadrado perfecto después de n^2 es (n+1)^2 = n^2 + 2n + 1, sabemos que la longitud de xyyz cae estríctamente entre los cuadrados consecutivos n^2 y (n+1)^2. Por tanto, la longitud de xyyz no puede ser un cuadrado perfecto. Pero si el lenguaje fuese regular, entonces xyyz tendría que estar en el lenguaje. Es decir, se contradice la suposición de que el lenguaje de cadena de ceros cuya longitud es n cuadrado perfecto es un lenguaje regular. LQQD.
fin de la traducción.
¿Cómo se podría caracterizar esa limitación en términos de memoria?
0 comentarios:
Publicar un comentario