Pumping lemma

La dimostrazione di non regolarità è più difficile del contrario, ma è possibile con il pumping lemma.

Il lemma esprime che se $A$ è regolare allora esiste $p\ge 1$ tale che se $s\in A$ e $|s|\ge p$ allora $s=xyz$ e:

1. $x{y}^{i}z\in A,\forall i\ge 0$
2. $|y|>0$
3. $|xy|\le p$

Dimostrazione

Essendo regolare esiste un DFA $D=(Q,\Sigma ,\delta ,q_0,F)$ tale che $L(D)=A$, allora si può scegliere come pumping length $p=|Q|$. Sia poi $s=w_1{w}_2\cdots w_n\in A$, allora:

• Se $n<p$, allora il teorema è vero perchè le condizioni non si applicano per queste stringhe

• Se $n\ge p$, allora $s$ è riconosciuta da una sequenza $q_0,q_1,...,q_n$, con $q_n\in F$:

  

  Dato che nella sequenza ci sono $n+1\ge p+1$ stati (perchè le $w_i$ sono gli archi), c'è almeno uno stato $q_i$ che si ripete (come in figura) e di conseguenza la prima e la seconda condizione sono verificate.

  Infine alla visita del $(p+1)$-esimo stato, $q_i$ si sarà sicuramente già ripetuto. Di conseguenza, il DFA avrà letto i primi $p$ caratteri che includono $xy$ (dato che $q_i$ si ripete su $y$), dimostrando la terza condizione.