Ogdens Lemma

Ogdens Lemma ist eine Methode der theoretischen Informatik, mit der gezeigt werden kann, dass eine formale Sprache keine kontextfreie Sprache ist, da sie Eigenschaften beschreibt die für alle kontextfreien Sprachen gelten. Das Pumping-Lemma der kontextfreien Sprachen ist ein Spezialfall von Ogdens Lemma.

Annahmen

Sei ${\mathcal {L}}_{2}$ die Menge aller Chomsky-Hierarchie-Typ-2-Grammatiken, welches somit die kontextfreien Sprachen bezeichnet.

Aussage

Sei $L$ eine kontextfreie Sprache, also $L\in {\mathcal {L}}_{2}$. Dann gibt es eine Konstante $n\in \mathbb {N}$, sodass für alle Wörter $z\in L$ mit $\left|z\right|\geq n$ folgende Aussage gilt: Es lassen sich in $z$ mindestens $n$ beliebige Buchstaben markieren und $z$ lässt sich in $z=uvwxy$ zerlegen, so dass gilt:

1. $vx$ enthält mindestens einen markierten Buchstaben
2. Die Anzahl der in $vwx$ markierten Buchstaben ist nicht größer als $n$
3. $\forall i\geq 0:uv^{i}wx^{i}y\in L$