Indietro

ⓘ Pumping lemma per i linguaggi liberi dal contesto




                                     

ⓘ Pumping lemma per i linguaggi liberi dal contesto

Il pumping lemma per i linguaggi liberi dal contesto, detto anche lemma di Bar-Hillel, è un lemma che fornisce una proprietà comune a tutti i linguaggi liberi dal contesto. Poiché descrive una condizione necessaria per lappartenenza di un linguaggio alla classe dei linguaggi liberi dal contesto, viene tipicamente utilizzato per dimostrare che un certo linguaggio non è context-free.

                                     

1. Descrizione formale

Se un linguaggio L è libero dal contesto, esiste un intero p > 0, dipendente esclusivamente dal linguaggio L, tale che qualsiasi stringa z in L con | z | ≥ p può essere scritta nella forma:

z = uvwxy

in modo tale che rispetti le seguenti regole:

  • |vwx| ≤ p ;
  • |vx| ≥ 1 al più uno tra v ed x è la parola vuota
  • uv i wx i y è in L per ogni i ≥ 0.

Inoltre, se L esclusa al più la parola vuota è il linguaggio generato da una grammatica in forma normale di Chomsky contenente n variabili, si può dimostrare il lemma per p = 2 n.

                                     

1.1. Descrizione formale Esempio

Dimostrazione che il linguaggio L ={a j b j c j: j > 0} non è libero dal contesto.

Si procede per assurdo assumendo il linguaggio L come libero da contesto. Sia p come dalla tesi del lemma. Poniamo z = a p b p c p. Poiché | z | = 3 p > p, per il pumping lemma z può esser scritta nella forma uvwxy dove | vwx | ≤ p, v e x non sono entrambe vuote e uv i wx i y è in L per ogni i ≥ 0. Poiché la a più a destra e la c più a sinistra di z distano p+1 posizioni, vwx può contenere al massimo due simboli distinti. Di conseguenza esiste un carattere fra a, b e c che compare meno di p volte in uwy, ne esiste un altro che compare p volte. Daltronde uwy appartiene a L per il pumping lemma, e ciò è assurdo perché tutte le stringhe di L hanno lo stesso numero di caratteri a, b, c. Si può concludere che lassunzione iniziale è falsa, e quindi L non è libero dal contesto.