Pumping lemma per i linguaggi regolari
Da Wikipedia, l'enciclopedia libera.
In Teoria dei linguaggi formali il pumping lemma per i linguaggi regolari è una proprietà che accomuna tutti i linguaggi regolari ed è condizione necessaria affinché un linguaggio sia regolare.
Viene utilizzato per dimostrare che un linguaggio NON è regolare.
[modifica] Descrizione Formale
Sia M = (Q, δ, q0, F) un automa accettore a stati finiti con n stati (|Q| = n) e sia z ∈ T(M), |z| ≥ n. T(M) è l'insieme delle parole accettato dall'automa a stati finiti M.
È quindi possibile scrivere z come uvw, e uv*x ⊂ T(M).
[modifica] Dimostrazione
Sia z = x1, x2... xk, z ∈ T(M).
Se si ha |z| ≥ n per essere accettata la parola prima di raggiungere lo stato di accettazione final deve passare per almeno n+1 stati ma, poiche' M ha solo n stati distinti almeno uno stato tra q0, qz1, qz2, ... qzk (stato finale in cui la parola z viene riconosciuta) deve comparire due volte.
Si supponga che sia qzi = qzj , i < j (cioe' che lo stato qzi sia quello in cui l'automa torna).
Poiché z ∈ T(M) l'automa M si porterà in uno stato finale per definizione all'ingresso di z=uvw ed è lo stesso in cui si porta M per effetto delle parole uw, uv2w, .... uviw, i ≥ 0 e quindi si ha che uviw ∈ T(M), i ≥0.
