Dubbio su pumping lemma

[lorenzoasr1]

Ciao a tutti,

avrei un dubbio riguardante la definizione del Pumping Lemma, che recita:

Se L è un Linguaggio Regolare, \(\displaystyle \exists n>0 \) tale che per \(\displaystyle \forall w \in L\) con \(\displaystyle |w| \geq n \), \(\displaystyle w = xyz \) dove:
1) \(\displaystyle |y| > 0 \)
2) \(\displaystyle |xy| \leq n \)
3) \(\displaystyle xy^iz \in L \forall i \geq 0 \)

Premesso che credo di aver capito l'idea dietro il Lemma, cioè che se supponiamo n essere il numero di stati dell'ipotetico DFA che accetta questo linguaggio allora devono esserci per forza delle ripetizioni di qualche stato, e di conseguenza un ciclo nel grafo che descrive l'esecuzione, il mio dubbio è sulla seconda condizione: per quale motivo è sufficiente considerare solo i cicli la cui etichetta compare entro n ?

[lorenzoasr1]

Credo di aver capito il motivo: noi siamo interessati a trovare una parola appartenente ad un linguaggio tale che questa sia più lunga del numero degli stati dell'eventuale DFA che la accetta e che non contenga nessun ciclo al suo interno, così da poter affermare che questo linguaggio è regolare.

In questo caso se un ciclo è presente si troverà entro i primi n simboli (con n numero degli stati dell'ipotetica DFA), e di conseguenza trovarne uno e verificarne la compatibilità con la terza condizione è sufficiente per dire che la parola in analisi non è funzionale al nostro scopo.