Pumping Lemma per CFG

Lemma

Se L è un linguaggio privo di contesto, c'è una lunghezza di pompaggio p tale che qualsiasi stringa w ∈ L di lunghezza ≥ p può essere scritto come w = uvxyz, dove vy ≠ ε, |vxy| ≤ pe per tutti i ≥ 0, uvⁱxyⁱz ∈ L.

Applicazioni del Pumping Lemma

Il pompaggio del lemma viene utilizzato per verificare se una grammatica è libera dal contesto o meno. Facciamo un esempio e mostriamo come viene controllato.

Problema

Scopri se la lingua L = {xⁿyⁿzⁿ | n ≥ 1} è contestuale o meno.

Soluzione

Permettere Lè privo di contesto. Poi,L deve soddisfare il pumping lemma.

All'inizio, scegli un numero ndel lemma pompante. Quindi, prendi z come 0 ⁿ 1 ⁿ 2 ⁿ .

Rompere z in uvwxy, dove

|vwx| ≤ n and vx ≠ ε.

Quindi vwxnon può coinvolgere sia 0 che 2, poiché l'ultimo 0 e il primo 2 sono almeno (n + 1) posizioni separate. Ci sono due casi:

Case 1 - vwxnon ha 2s. Poivxha solo 0 e 1. Poiuwy, che dovrebbe essere in L, ha n 2s, ma meno di n 0 o 1.

Case 2 - vwx non ha 0.

Qui si verifica una contraddizione.

Quindi, L non è una lingua priva di contesto.