Pumping Lemma per il linguaggi regolari

Pumping lemma per i linguaggi regolari

Enunciato

Sia M = (Q, δ, q, F) un automa accettare a stati finiti con n stati (|Q| = n) e sia z un elemento di T(M), con |z| ≥ n. Allora z può essere scritto come uvw e uwⁱ appartiene a T(M) per ogni i, i ≥ 0.

Dimostrazione

Sia x, z un elemento di T(M). Sia z = x₁x₂...x_k. Al termine della stringa, l’automa si sarà portato nello stato q_k dopo la lettura del terminale x, che provoca la transizione nello stato q.

Per ipotesi, abbiamo scelto z in modo tale che la sua lunghezza sia maggiore di n (n = numero di stati dell’automa). Poiché il numero degli stati è uno in più rispetto al numero di transizioni (una transizione: da q₀ a q₁ (ci sono tre stati), ecc.), l’automa accettore avrà k stati, quindi l’automa che riconosce z con |z| ≥ n avrà almeno n + 1 stati.

Però per ipotesi abbiamo stabilito che il numero degli stati è n (|Q| = n). Questo significa che almeno due stati sono coincidenti e quindi è presente un ciclo. Siano q_i e q_j gli stati coincidenti con i < j. La lunghezza del ciclo è quindi pari a j - i.

L’automa è allora del tipo rappresentato in figura. Possiamo allora suddividere la stringa accettata in tre parti:

• u = x₁x₂...x_i, |u| = i (parte iniziale)
• v = x_i+1x_i+2...x_j, |v| = j - i (lunghezza ciclo)
• w = x_j+1x_j+2...x_n, |w| = n - j (parte finale)

Si noti che l’automa si porta nello stato finale anche evitando il ciclo oppure percorrendolo più volte. Nel primo caso la stringa accettata sarà uw ( = uv⁰w), mentre nel secondo sarà uv^pw dove p è il numero di volte che viene eseguito il ciclo.

Inoltre |uv| ≤ n (precisamente |uv| = j) perché percorro la parte iniziale, eseguo il ciclo una sola volta senza la parte finale non usando quindi tutti gli stati, ed infine |v| ≠ 0 perché come detto precedentemente il ciclo esiste ed è lungo j-i.