Ogdens Lemma

I formel sprogteori giver Ogdens lemma en udvidelse af fleksibiliteten af ​​sprawl-lemmaet for kontekstfrie sprog .

Ogden Lemma siger, at hvis sproget L er kontekstfrit, så eksisterer der et eller andet tal p > 0 (hvor p kan eller ikke kan være pumpelængden), således at for enhver streng w af længde mindst p fra L og for evt . "markup" p eller flere positioner i w , w kan repræsenteres som

hvor u , v , x , y og z  er strenge sådan

1. x indeholder mindst én mærket position,
2. enten indeholder både u og v den markerede position, eller både y og z indeholder den ,
3. vxy indeholder højst p markerede positioner, og
4. uv i xy i z hører til L for enhver i ≥ 0.

Ogdens Lemma kan bruges til at bevise, at et givet sprog ikke er kontekstfrit, i tilfælde hvor vækstlemmaet for kontekstfri sprog ikke er tilstrækkeligt. Et eksempel ville være sproget { a i b j c k d l  : i = 0 eller j = k = l }. Det er også nyttigt til at bevise den væsentlige tvetydighed i nogle sprog.

Bemærk, at hvis alle positioner er markeret, svarer dette lemma til det pumpende lemma for kontekstfrie sprog.

Se også

• Vækstlemma for kontekstfrie sprog
• Vækst Lemma