Wofür ist das Pumping Lemma ein Lemma?

8

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?

Arya
quelle

Antworten:

9

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 nnn2n

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).{0n10n:n0}

Yuval Filmus
quelle