This post has been edited 2 times, last edit by "Thomas" (Mar 3rd 2006, 11:21am)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
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.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.
Insbesondere ist sogar jede endliche Sprache regulär.Quoted
d.h. es gibt auch endliche kontextfreie sprachen.