Ogdens Lemma

2015-09-24T10:10:03Z

178.24.74.113: Die Bedingung, dass vw mindestens einen markierten Buchstaben enthielte war wohl ein Tippfehler, richtig ist, wie auch im unterem Abschnitt erwähnt, dass dies für vx gilt.

'''Ogdens Lemma,''' benannt nach [[William Ogden]], ist eine Methode der [[theoretische Informatik|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 müssen. Es liefert somit nur eine notwendige (keine hinreichende) Bedingung für die Klassifikation als kontextfreie Sprache. Ogdens Lemma ist also nicht geeignet um Kontextfreiheit zu beweisen.

Das [[Pumping-Lemma]] ist ein Spezialfall von Ogdens Lemma.

== Aussage ==

Sei <math>\mathcal{L}_2</math> die Klasse aller Sprachen, die sich von [[Chomsky-Hierarchie]]-Typ-2-Grammatiken erzeugen lassen, also die Klasse der kontextfreien Sprachen.

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

# <math>vx</math> mindestens einen markierten Buchstaben enthält,
# <math>vwx</math> maximal <math>n</math> markierte Buchstaben enthält,
# <math>\forall i \ge 0: uv^iwx^iy \in L</math>.

== Beispiel ==

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

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

'''[[Reductio ad absurdum|Beweis durch Widerspruch]]:''' Wir nehmen an, <math>L</math> sei kontextfrei. Dann existiert nach Ogdens Lemma eine Konstante <math>n</math>, so dass für jedes Wort <math>z\in L</math> und jede Markierung, die mindestens <math>n</math> Zeichen in <math>z</math> markiert, eine Zerlegung existiert, die die Eigenschaften 1., 2. und 3. erfüllt.

Die Konstante sei also <math>n</math> und insbesondere für das Wort <math>z=ab^nc^nd^n\in L</math> mit Markierung auf dem Teil <math>b^n</math> muss es eine Zerlegung <math>z=uvwxy</math> geben, die 1., 2. und 3. erfüllt.

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

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

Wir führen also Eigenschaft 3. stets mit <math>i=2</math> zum Widerspruch, da das Wort <math>uv^2wx^2y</math> nicht in <math>L</math> 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.

[[Kategorie:Theorie formaler Sprachen]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Ogdens Lemma