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:
- vx contiene almeno una posizione marcata;
- vwx ha al massimo p posizioni marcate
- 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.
Bibliografia[modifica | modifica wikitesto]
- 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.