Pumping Lemma con dimostrazione

Enunciato del pumping lemma

Se un linguaggio è regolare, allora esiste una costante p (dipendente da L) tale che, per ogni stringa s nel linguaggio L con lunghezza almeno p, possiamo scomporre s in tre stringhe, x, y, z, con le seguenti tre proprietà:

• y ≠ ε
• |xy| ≤ p
• Per ogni i ≥ 0, xyⁱz è nel linguaggio L

Dimostrazione del pumping lemma

Sia Σ un alfabeto e L un linguaggio regolare su Σ. Poiché L è regolare, esiste un DFA (Automa a Stati Finiti Deterministico) che lo accetta. Poniamo che il numero di stati del DFA sia pari a n. Sia p = n.

Consideriamo una stringa s di lunghezza almeno p. La computazione del DFA su s attraversa p+1 stati. Poiché ci sono solo n stati e la computazione attraversa p+1 stati, deduciamo che ci deve essere uno stato che viene visitato almeno due volte nelle prime p posizioni della computazione.

Esistono allora due indici i e j, con 0 ≤ i < j ≤ p, tali che lo stato q viene visitato all'indice i e all'indice j. Spezziamo s in tre stringhe x, y, z così fatte:

• x = s[0:i]
• y = s[i:j]
• z = s[j:]

Graficamente:

s = xyz

Verifica delle proprietà

• 1. y ≠ ε: Poiché i < j, y deve contenere almeno un simbolo, quindi y ≠ ε.
• 2. |xy| ≤ p: Dato che j ≤ p, abbiamo |xy| = j ≤ p.
• 3. xyⁱz ∈ L per ogni i ≥ 0: Modificando il numero di ripetizioni di y non cambia l'accettazione della stringa da parte del DFA, quindi xyⁱz è sempre nel linguaggio L.

Abbiamo quindi dimostrato che, se un linguaggio è regolare, allora deve soddisfare il pumping lemma.