Pumping lemma per i linguaggi liberi dal contesto

Da Wikipedia, l'enciclopedia libera.

Il pumping lemma per i linguaggi context-free viene utilizzato per dimostrare che un certo linguaggio non è context-free.

[modifica] Descrizione formale

Se un linguaggio L è infinito e context-free esisterà un intero p>0 dipendente esclusivamente dal linguaggio L tale che qualsiasi stringa z in L con |z| > p (con cardinalità maggiore di p) può essere scritta nella forma:

z = uvwxy

in modo tale che rispetti le seguenti regole:

|vwx| < p;
|vx| ≠ λ (al piu' uno tra v ed x e' la parola vuota)
uvⁱwxⁱy ∈ L ∀ i ≥ 0 (v ed x sono le stringhe che devono essere "pompate" un numero arbitrario di volte, compreso 0, e la parola che ne deriva è ancora una appartenente al linguaggio L)

[modifica] Esempio

Dimostrazione che il linguaggio L={a^jb^jc^j: j>0} non è context free.

Si procede per assurdo assumendo il linguaggio L come libero da contesto prendendo in considerazione le ipotesi di cui sopra.

Se la stringa z ∈ L dove |z| > p la parola z può esser scritta nella forma uvwxy dove |vwx| ≤ p
Ora si sceglie un valore per p ≥ j.
Ora, ad ogni occorrenza di vwx nella stringa a^pb^pc^p, vwx puo' contenere al piu' due simboli distinti dal momento che la a più a destra secondo l'algoritmo dista j+1 posizioni dalla c più a sinistra.
1. Esempio: la parola vwx può essere composta da tutte a, tutte b, tutte c, da sole a e b, o b e c.
  1. Quindi la stringa vwx può contenere al più due simboli distinti
Dal momento che uvwxy ∈ L, uv²wx²y ∈ L. Dal momento che, come stabilito dalle regole, al piu' una tra v ed x e' la stringa vuota, |uv²wx²y| > |uvwxy|, quindi sono state aggiunte lettere.
Ma dal momento che vwx non contiene tre lettere distinte, e' impossibile che sia stato aggiunto lo stessa quantita' di ogni lettera. Abbiamo "pompato" piu' lettere e contraddetto la definizione originale di L.
Quindi uv²wx²y ∉ L e si è arrivati ad una contraddizione.
Ne deriva che l'asserzione originale, L Context Free è falsa.