1) Sea L = { 0^n | n = 2^p }
2) Sea h, |w| >= h, h = 2^p p >= 0
1) Sea w = 0^(p 0)0^(p 1)0^(p 2) ... 0^(p p), donde (p i) es la combinatoria de p tomados de i en i. Es decir, estamos usando los coeficientes combinatorios como las "potencias". El objetivo es usar el hecho de que 2^p = Sumatoria desde i = 0 hasta p de (p i).
2) Sea x = 0^(p 1)..0^(p k-1) ; y = 0^(p k) ; z = 0^(p k+1)..0^(p p). Noten que y no es vacía y |xy| < h, verdad?
1) Sea k=0, cualquiera que sea la longitud correspondientes de 0^(p 1)..0^(p k-1) 0^(p k+1)..0^(p p) es menor que 2^p, por lo que NO pertenece a L. LQQD.
2) Sea h, |w| >= h, h = 2^p p >= 0
1) Sea w = 0^(p 0)0^(p 1)0^(p 2) ... 0^(p p), donde (p i) es la combinatoria de p tomados de i en i. Es decir, estamos usando los coeficientes combinatorios como las "potencias". El objetivo es usar el hecho de que 2^p = Sumatoria desde i = 0 hasta p de (p i).
2) Sea x = 0^(p 1)..0^(p k-1) ; y = 0^(p k) ; z = 0^(p k+1)..0^(p p). Noten que y no es vacía y |xy| < h, verdad?
1) Sea k=0, cualquiera que sea la longitud correspondientes de 0^(p 1)..0^(p k-1) 0^(p k+1)..0^(p p) es menor que 2^p, por lo que NO pertenece a L. LQQD.
0 comentarios:
Publicar un comentario