[LF] pumping lemma

[_overflow_1]

Ciao a tutti!!!

devo dimostrare che $L={a^ib^j | i=2^j, i, j>=0}$ non è libero dal contesto applicando il pumping lemma...
Ho provato, però mi sono bloccato, allora sono andato a vedere la soluzione sul libro, tuttavia non mi è chiaro un passaggio.
Il libro procede in questo modo:
dopo aver fatto tutte le premesse del caso dice:
Consideriamo la parola $z=(a^2)^pb^p$

$zinL$ ed inoltre $|z|=2^p+p>p$

Per il PL quindi si può scrivere $z=uvwxy$ ove $|vwx|<=p$ consideriamo ora la stringa $uv^2wx^2y$ che per le premesse di prima deve appartenere a $L$
Ma:
$|uv^2wx^2y|=|uvwxy|+|vx|<=|uvwxy|+|vwx|<=2^p+p+p<=2^p+2^p+p=2*2^p+p=2^(p+1)+p<2^(p+1)+p+1$
Arrivando così all'assurdo dato che la stringa "pompata" non appartiene a $L$.

Ora il passaggio che non mi è chiaro è questo:
$...2^p+p+p<=2^p+2^p+p...$
da dove lo prende $2^p+2^p+p$

Non ho capito molto il procedimento, ringrazio tutti anticipatamente.

[Gi81]

Si è sfruttata una proprietà matematica: $p<=2^p$ $AA p in NN$
Quindi $2^p+p+p<=2^p+2^p+p$

[_overflow_1]

azz vero
ti ringrazio...
in questo modo quindi ha dimostrato che $|uv^2wx^2y|<2^(p+1)+p+1$ inoltre $|uv^2wx^2y|=|z|+|vx|>|z|=2^p+p$ ed essendo perciò $|uv^2wx^2y|$ compreso tra quelle due quantità non appartiene al linguaggio, giusto?

[Gi81]

Esattamente

[_overflow_1]

Grazie mille

[zup1]

Ciao Overflow,
ho il tuo stesso problema e ti ho seguito fino a quando hai affermato
"ed essendo perciò ∣∣uv2wx2y∣∣ compreso tra quelle due quantità non appartiene al linguaggio, giusto?"
mi puoi chiarire questa tua conclusione ?

grazie