Fachrat Informatik - Forum

grundsätzlich gilt: mit dem pumping-lemma kannst du nur beweisen, dass eine sprache nicht(!) kontextfrei ist; nichts anderes. wenn du also kein wort findest, dass du entsprechend (siehe definition) aufpumpen kannst, dann ist die vorliegende sprache nicht kontextfrei.


nun zu deinem problem. aus dem pumping-lemma:
... es gibt eine natürliche zahl n, so dass sich alle wörter der sprache L, die länger sind als n oder gleich lang, aufpumpen lassen mit den drei bekannten eigenschaften...

nimm dir die kontextfreie sprache L={a} als beispiel. L ist kontextfrei (auch regulär) und endlich. du wählst z.b. n=55. da es aber keine wörter in L, die länger als 54 zeichen sind, gibt, bist du mit dem pumping-lemma fertig. und die eigenschaft ist für diese kontextfreie sprache erfüllt.

d.h. es gibt auch endliche kontextfreie sprachen.

Quoted

Original von Thomas
grundsätzlich gilt: mit dem pumping-lemma kannst du nur beweisen, dass eine sprache nicht(!) kontextfrei ist; nichts anderes. wenn du also kein wort findest, dass du entsprechend (siehe definition) aufpumpen kannst, dann ist die vorliegende sprache nicht kontextfrei.

Es ist ein wenig anders: Wenn Du ein Wort findest (geeigneter Länge), daß Du nicht wie im Pumping-Lemma für kontextfreie Sprachen beschrieben "aufpumpen" kannst, dann ist die vorliegende Sprache nicht kontextfrei.

Mit dem Pumping-Lemma läßt sich zudem nicht für jede nicht-kontextfreie Sprache beweisen, daß sie nicht kontextfrei ist.

Quoted

d.h. es gibt auch endliche kontextfreie sprachen.

Insbesondere ist sogar jede endliche Sprache regulär.