Ogden's Lemma

[Morpheus_/_Neo]

Ciao a tutti, sto preparando l'esame di Informatica Teorica e mi e' venuto un dubbio riguardante il lemma di Ogden.

Lemma: dato un linguaggio context-free L, esiste una costante n dipendente solo da L tale che se z appartiene a L e |z| >= n allora z = uvwxy e posso scegliere su z n o piu' posizioni in modo che
1. vx contiene almeno una posizione tra quelle scelte
2. vwx contiene al piu' n delle posizioni scelte
3. per ogni i u(v^i)w(x^i)y appartiene a L

Dubbio: come si dimostra il punto 2?????

grazie a tutti
M_/_N