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 uvⁱ u′ ebenfalls in L sind.

Die Nichtregularität der Sprache {aⁿ bⁿ | n ≥ 1} kann damit gezeigt werden, weil bei der Zerlegung von aⁿ bⁿ der mittlere Teil v entweder die Form a^k, b^k, oder a^k b^j haben muß. In allen Fällen ist uvvu′ nicht Element der Sprache (nämlich a^n+k bⁿ, aⁿ b^n+k bzw. aⁿ b^j a^k bⁿ).