[RISOLTO, Esercizio] Pumping Lemma Context-Free

[TheDarkM@n]

salve scusate ma sto diventando matto su un esercizio, come si dimostra tramite il Pumping Lemma che il seguente linguaggio NON è context-free
\(\displaystyle L=\left \{ ww|w\in c(a+b)^{*}c \right \} \)

in sostanza la parola sarebbe \(\displaystyle c(a+b)^{n}cc(a+b)^{n}c \) con \(\displaystyle n\geq 0\) (sarebbe la parola \(\displaystyle c(a+b)^{*}c \) concatenata con se stessa)

[Dante.utopia]

Per assurdo, supponiamo che $L$ sia context-free, allora per il Pumping-Lemma

$\exists n \geq 0$ tale che, $\forall z \in L$ con $|z| \geq n$ allora $z$ può essere scritta come:

$z=uvwxy$ dove $|vwx| \leq n$ e $|vx| \geq 1$ con la proprietà

$\forall i \geq 0$ la parola $u v^i w x^i y \in L$.

Mettiamo:

$u=c(a+b)^\ast $
$v=c$
$w=\epsilon$
$x=c$
$y=(a+b)^\ast c$

verifichiamo che $|vwx| = |c \epsilon c| = 2$ da cui $n \geq 2$ ok
e che $|vx|=| c c|=2 \geq 1$ ok

allora $\forall i$ deve essere $u v^i w x^i y = c(a+b)^\ast c^i \epsilon c^i (a+b)^\ast c$ una parola del linguaggio.

Ma vediamo che questo è falso poiché ad esempio la parola per $i=2$

$c(a+b)^\ast c c c c (a+b)^\ast c$ non appartiene a $L$, quindi la nostra ipotesi; L è context-free non può che essere falsa.

[TheDarkM@n]

sei stato no chiaro... di più! grazie mille