100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 7: Pumping Lemma

Der vorliegende Vorlesungszuschnitt beschäftigt sich mit dem Pumping-Lemma (PPL) für reguläre Sprachen und dem PPL für kontextfreie Sprachen. Das PPL ist eine Eigenschaft, die alle Sprachen der jeweiligen zugehörigen Sprachklasse besitzen. Es macht Aussagen über Sprachen, deren Wörter strukturell nach einfachen Prinzipen definiert werden können. Für solche Sprachen gilt, dass sie, wenn sie Wörter einer bestimmten Mindestlänge enthalten, automatisch eine unendliche Menge weiterer Wörter enthalten müssen, die sich durch das ?Aufpumpen? der vorhandenen Wörter ergeben. Dabei orientiert sich die Vorlesung bei der Formulierung des PPLs bei regulären Sprachen an endlichen Automaten, bei kontextfreien Sprachen werden kontextfreie Grammatiken betrachtet. Es wird erklärt, wie anhand des entsprechenden PPLs Nachweise der Nicht-Regularität bzw. Nicht-Kontextfreiheit einer Sprache durchgeführt werden können.