Dies ist etwas, das ich nicht finden konnte - aber ich fand es immer interessant, dass das Pump-Lemma nur ein Lemma ist (zumal es den gleichen Namen für reguläre Sprachen, kontextfreie Sprachen usw. hat).
Was ist das für ein Lemma?
Dies ist etwas, das ich nicht finden konnte - aber ich fand es immer interessant, dass das Pump-Lemma nur ein Lemma ist (zumal es den gleichen Namen für reguläre Sprachen, kontextfreie Sprachen usw. hat).
Was ist das für ein Lemma?
In der Grundlagenarbeit von Rabin und Scott, Finite Automaten und ihren Entscheidungsproblemen erscheint das Pump-Lemma als Lemma (Lemma 8) für das folgende Ergebnis (Satz 9):
Die von einem DFA mit Zuständen akzeptierte Sprache ist genau dann unendlich, wenn sie ein Wort akzeptiert, dessen Länge zwischen und .n 2 n
Das Pump-Lemma impliziert die Richtung.
Es gibt auch "einen weiteren Beweis", dass die Sprache nicht regelmäßig ist (der ursprüngliche Beweis in der Arbeit verwendet die Myhill-Nerode-Theorie).