Ogdens Lemma

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

Es liefert also eine notwendige Bedingung jeder kontextfreien Sprache.

Das Pumping-Lemma (= Pumplemma) der kontextfreien Sprachen ist ein Spezialfall von Ogdens Lemma.

[Bearbeiten] Annahmen

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

[Bearbeiten] Aussage

Sei $L$ eine kontextfreie Sprache, also $L \in \mathcal{L}_2$ . Dann gibt es eine Konstante $n \in \mathbb{N}$ , so dass für alle Wörter $z \in L$ mit $\left| z \right| \ge n$ folgendes gilt: Wenn in $z$ mindestens $n$ Buchstaben markiert werden, so lässt sich $z$ als $z = u v w x y$ in fünf Teile zerlegen, so dass

in $v x$ mindestens ein Buchstabe markiert ist und
in $v w x$ höchstens n Buchstaben markiert sind und
$\forall i \ge 0: uv^iwx^iy \in L$ .

[Bearbeiten] Beispiel

Die Sprache $L = \{a^ib^jc^kd^{\ell}\ |\ i\neq 0\ \Rightarrow\ j=k=\ell\}$ ist nicht kontextfrei.

Der Nachweis, dass $L$ nicht kontextfrei ist, kann nicht mit dem Pumping-Lemma für kontextfreie Sprachen geführt werden, aber mit Ogdens Lemma.

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

Die Konstante sei also $n$ und insbesondere für das Wort $z=ab^nc^nd^n\in L$ mit Markierung auf dem Teil $b n$ muss es eine Zerlegung $z = u v w x y$ geben, die 1., 2. und 3. erfüllt.

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

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