Lexikon der Mathematik: Pumping-Lemma für reguläre Sprachen
Aussage über reguläre Sprachen, die insbesondere zur Widerlegung der Regularität benutzt wird.
Zu jeder regulären Sprache L ⊆ Σ∗gibt es ein n ∈ ℕ so, daß sich jedes Wort w, das in L und länger als n ist, in drei Wörter u, v und u′ zerlegen läßt (w = uvu′ ), wobei die Länge von u höchstens n und die Länge von v mindestens 1 ist, und alle Wörter der Form uvi u′ ebenfalls in L sind.
Die Nichtregularität der Sprache {an bn | n ≥ 1} kann damit gezeigt werden, weil bei der Zerlegung von an bn der mittlere Teil v entweder die Form ak, bk, oder ak bj haben muß. In allen Fällen ist uvvu′ nicht Element der Sprache (nämlich an+k bn, an bn+k bzw. an bj ak bn).
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.