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 є T(M), |z| ≥ n. Allora z può0  T(M), cioè per ogni i, i ≥ 0 : uv w єiessere scritta come uvw e uw*w T(M). Dimostrazione: …x , z є T(M) Sia z =x x1 2 k al termine della stringa l’automa si sarà La lettura del terminale x provoca la transizione nello stato q ,quindii iportato nello stato q .k Per ipotesi abbiamo scelto z in modo tale che la sua lunghezza sia maggiore di n (n = numero di statidell’automa). Poiché il numero degli stati è uno in più rispetto al numero di transizioni (una transizione: da q a q (ci sono0 1(ci sono tre stati), ecc..), l’automa accettore …xdue stati), due transizioni: da q a q , da q a q per x x avrà k0 1 1 2 1 2 k1 stati, quindi l’automa che riconosce z con |z| ≥ n avrà almeno n + 1 stati. +Però per ipotesi abbiamostabilito che il numero degli stati è n (|Q| = n). Questo significa che almeno due stati sono coincidenti e quindi è presente un ciclo. Siano q e q' 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: ...

Infine |v| ≠ 0 perché, come detto precedentemente, il percorso del ciclo esiste ed è lungo j-i.