hola:
elegida la tira z, uno tiene que probar que, para todas las posibles descomposiciones de esa tira, no se cumple alguna de las tres propiedades (i), (ii) y (iii) (perdón si no las escribo pero esto sería muy largo).
inclusive restringiéndonos a aquellas que cumplen (i) y (ii), no podríamos escribir la totalidad de las descomposiciones, básicamente porque el largo de la tira es N. para fijar ideas, en tu ejemplo y con la tira de la solución tendría que considerar:
u = 10
v = 0
w = 0^2N (01)^2N+1
pero también
u = 100 v = 0 w = 0^2N-1 (01)^2N+1
y
u = 100 v = 0000 w = 0^2N-4 (01)^2N+1
y así sucesivamente... no solo engorroso, sino imposible, sobre todo porque no conozco el N. entonces lo que se hace es agrupar en "familias", esto es, descomposiciones sintácticamente parecidas se las "parametriza" en las cantidades, para probar de un saque todas las variantes. las anteriores se corresponden con la familia 2 de la solución: p=q=1, p=2 y q=1, p=2 y q=4. con esa familia pruebo las 3 descomposiciones anteriores, y todas las variaciones de largos posibles parametrizadas con p y q.
pero ¿por qué se plantea una familia 1 con u=éps? porque todas las descomposiciones abarcadas en la familia anterior obligan a que u empiece con un 1. esto deja afuera a descomposiciones como:
u = épsilon v=10000 w = 0^2N-2 (01)^2N+1
o
u = épsilon v=1 w = 0^2N+2 (01)^2N+1
es por eso que se plantea una nueva familia (caso 1 de la solución), en donde las descomposiciones anteriores están contempladas con q=4 y q=0 respectivamente.
" Esto se puede hacer siempre?"
como poder, se puede hacer. también se pueden plantar mil descomposiciones distintas... unas con v de largo par y otras con v de largo impar... pero la idea es, precisamente, reducir la cantidad de familias posibles! cuantas más familias, más cosas para probar (y menos tiempo para resolver otras en el parcial).
por ejemplo, por qué no se aplica en el caso famoso del teórico con un z=0^N 1^N? porque esa descomposición ya está considerada en:
u= 0^p v = 0^q w = 0^N-p-q 1^N
cuando p=0
"no estaría faltando la descomposición donde u = 0?"
la respuesta es no. recordá que u.v.w es una descomposición de z y la z elegida comienza por 1 (todas las tiras del lenguaje empiezan con 1 y esa es una condición que debe cumplir z). si u fuese la tira "0", estarías diciendo que z = u... = 0... no pertenece al lenguaje (esto es, ninguna descomposición de z va a tener una u comenzando por 0)
saludos,
d.-