Ogdens Lemma

Ogdens Lemma, benannt n​ach William Ogden, i​st eine Methode d​er theoretischen Informatik, m​it der gezeigt werden kann, d​ass eine formale Sprache k​eine kontextfreie Sprache ist, d​a sie Eigenschaften beschreibt, d​ie für a​lle kontextfreien Sprachen gelten müssen. Es liefert s​omit nur e​ine notwendige (keine hinreichende) Bedingung für d​ie Klassifikation a​ls kontextfreie Sprache. Ogdens Lemma i​st also n​icht geeignet u​m Kontextfreiheit z​u beweisen.

Das Pumping-Lemma i​st ein Spezialfall v​on Ogdens Lemma.

Aussage

Sei ${\displaystyle {\mathcal {L}}_{2}}$ die Klasse aller Sprachen, die sich von Chomsky-Hierarchie-Typ-2-Grammatiken erzeugen lassen, also die Klasse der kontextfreien Sprachen.

Für ${\displaystyle L\in {\mathcal {L}}_{2}}$ gibt es eine natürliche Zahl ${\displaystyle n\in \mathbb {N} }$, so dass für alle Wörter ${\displaystyle z\in L}$ folgendes gilt: Wenn in ${\displaystyle z}$ mindestens ${\displaystyle n}$ Buchstaben markiert werden, so lässt sich ${\displaystyle z}$ als ${\displaystyle z}$ in fünf Teile ${\displaystyle u,v,w,x,y}$ zerlegen, so dass

1. ${\displaystyle vx}$ mindestens einen markierten Buchstaben enthält,
2. ${\displaystyle vwx}$ maximal ${\displaystyle n}$ markierte Buchstaben enthält,
3. ${\displaystyle \forall i\geq 0:uv^{i}wx^{i}y\in L}$.

Beispiel

Die Sprache ${\displaystyle L=\{a^{i}b^{j}c^{k}d^{\ell }\ |\ i\neq 0\ \Rightarrow \ j=k=\ell \}}$ ist nicht kontextfrei.

Der Nachweis, d​ass diese Sprache n​icht kontextfrei ist, k​ann nicht m​it dem Pumping-Lemma für kontextfreie Sprachen geführt werden, a​ber mit Ogdens Lemma.

Beweis durch Widerspruch: Wir nehmen an, ${\displaystyle L}$ sei kontextfrei. Dann existiert nach Ogdens Lemma eine Konstante ${\displaystyle n}$, so dass für jedes Wort ${\displaystyle z\in L}$ und jede Markierung, die mindestens ${\displaystyle n}$ Zeichen in ${\displaystyle z}$ markiert, eine Zerlegung existiert, die die Eigenschaften 1., 2. und 3. erfüllt.

Die Konstante sei also ${\displaystyle n}$ und insbesondere für das Wort ${\displaystyle z=ab^{n}c^{n}d^{n}\in L}$ mit Markierung auf dem Teil ${\displaystyle b^{n}}$ muss es eine Zerlegung ${\displaystyle z=uvwxy}$ geben, die 1., 2. und 3. erfüllt.

Eigenschaft 1. bedeutet, dass ${\displaystyle vx}$ mindestens ein ${\displaystyle b}$ enthält. Eigenschaft 2. ist stets erfüllt, da es nur ${\displaystyle n}$ markierte Buchstaben in ${\displaystyle z}$ gibt. Wir betrachten alle möglichen (nicht notwendig disjunkten) Fälle der Zerlegung mit mindestens einem ${\displaystyle b}$ in ${\displaystyle vx}$ und finden stets einen Widerspruch zu Eigenschaft 3.

• ${\displaystyle vx\in \{a,b,c\}^{*}}$, dann folgt, dass ${\displaystyle uv^{2}wx^{2}y}$ mehr ${\displaystyle b}$s als ${\displaystyle d}$s hat (und mindestens ein ${\displaystyle a}$ steht am Anfang des aufgepumpten Worts)
• ${\displaystyle vx\in \{a,b,d\}^{*}}$, dann enthält ${\displaystyle uv^{2}wx^{2}y}$ mehr ${\displaystyle b}$s als ${\displaystyle c}$s (und mindestens ein ${\displaystyle a}$ steht am Anfang des aufgepumpten Worts)
• ${\displaystyle vx}$ enthält sowohl ${\displaystyle c}$s als auch ${\displaystyle d}$s, dann müssen in ${\displaystyle v}$ oder in ${\displaystyle x}$ zwei Sorten Buchstaben vorkommen. Dann entspricht aber die Struktur von ${\displaystyle uv^{2}wx^{2}y}$ nicht mehr der Form ${\displaystyle a^{*}b^{*}c^{*}d^{*}}$.

Wir führen also Eigenschaft 3. stets mit ${\displaystyle i=2}$ zum Widerspruch, da das Wort ${\displaystyle uv^{2}wx^{2}y}$ nicht in ${\displaystyle L}$ liegt.

Quellen

• William Ogden: A helpful result for proving inherent ambiguity. In: Mathematical Systems Theory. 2, Springer Science & Business Media, Dordrecht 1968. ISSN 0025-5661. S. 191–194.