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 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 formale
modificaSe 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)
- uviwxiy è 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 = 2n.
Esempio
modificaDimostrazione 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
modifica- Y. Bar-Hillel, Perles, M. e Shamir, E., On formal properties of simple phrase-structure grammars, in Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung, vol. 14, 1961, pp. 143–177.
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997, ISBN 0-534-94728-X. Sezione 1.4: Nonregular Languages, pp. 77–83. Sezione 2.3: Non-context-free Languages, pp. 115–119.
- J.E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001, ISBN 0-534-94728-X.
