Lemma di Ogden

Da Wikipedia, l'enciclopedia libera.

Nella teoria dei linguaggi formali, il lemma di Ogden è una generalizzazione del pumping lemma per i linguaggi liberi dal contesto.

Il lemma di Ogden afferma che se L è un linguaggio libero dal contesto, allora esiste un intero p > 0 tale che per ogni stringa z di lunghezza almeno p in L e ogni modo di "marcare" p o più posizioni all'interno di z, si può scrivere z come

z = uvwxy

dove le stringhe u, v, w, x, e y soddisfano le seguenti condizioni:

  1. vx contiene almeno una posizione marcata;
  2. vwx ha al massimo p posizioni marcate
  3. uviwxiy appartiene ad L per ogni i > 0.

Nel caso particolare in cui tutte le posizioni di z sono marcate, questo risultato si riduce al pumping lemma per i linguaggi liberi dal contesto.

Il lemma di Ogden permette di dimostrare la non-appartenenza di certi linguaggi alla classe dei linguaggi liberi dal contesto, anche in alcuni casi in cui il pumping lemma non è sufficiente. Un esempio è il linguaggio {aibjckdl : i = 0 oppure j = k = l}. È utile anche per dimostrare l'inerente ambiguità di alcuni linguaggi.

Voci correlate[modifica | modifica sorgente]

Riferimenti[modifica | modifica sorgente]

  • William Ogden, A helpful result for proving inherent ambiguity in Mathematical Systems Theory, vol. 2, 1968, pp. 191–194, DOI:10.1007/BF01694004.