|
Pumping lemma per i linguaggi liberi dal contestoIl 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 l'appartenenza di un linguaggio alla classe dei linguaggi liberi dal contesto, viene tipicamente utilizzato per dimostrare che un certo linguaggio non è context-free. Descrizione formaleSe 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:
in modo tale che rispetti le seguenti regole:
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 = 2n. EsempioDimostrazione che il linguaggio L={ajbjcj: 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 = apbpcp. Poiché |z| = 3p > p, per il pumping lemma z può esser scritta nella forma uvwxy dove |vwx| ≤ p, v e x non sono entrambe vuote e uviwxiy è 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, e ne esiste un altro che compare p volte. D'altronde 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 l'assunzione iniziale è falsa, e quindi L non è libero dal contesto.
Bibliografia
Voci correlate |
