Lemma di Ogden

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. uv^iwx^iy 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 {a^ib^jc^kd^l : i = 0 oppure j = k = l}. È utile anche per dimostrare l'inerente ambiguità di alcuni linguaggi.

Bibliografia

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

• J.E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001, ISBN 0-534-94728-X.

Voci correlate

• Pumping lemma per i linguaggi liberi dal contesto
• Pumping lemma per i linguaggi regolari