Sprachen, die das Pumplemma erfüllen, aber nicht regelmäßig sind?

Wenn eine reguläre Sprache , ist es leicht zu beweisen, dass es eine Konstante N gibt, die σ ∈ L ist , mit | σ | ≥ N gibt es Zeichenketten α , β und γ, so dass | α β | ≤ N und | β | & Ne; & egr; und für alle k ist & agr; & bgr; k & ggr; ∈ $L$$N$$\sigma \in L$$\lvert \sigma \rvert \ge N$$\alpha$$\beta$$\gamma$$\lvert \alpha \beta \rvert \le N$$\lvert \beta \rvert \ne \epsilon$$k$$\alpha \beta^k \gamma \in L$. Es ist allgemein bekannt, dass das Gegenteil nicht der Fall ist, aber ich habe kein klares Beispiel dafür gesehen. Irgendwelche Vorschläge? Es ist klar, dass der Beweis, dass die beleidigende Sprache nicht regelmäßig ist, stärkere Methoden anwenden muss als das typische "befriedigt das pumpfähige Lemma nicht". Ich würde mich für einfache Beispiele interessieren, um sie in einführenden formalen Sprachkursen zu präsentieren.

Die Sprache scheint einfach zu sein. Der zweite Teil ist regulär (und kann gepumpt werden). Der erste Teil ist unregelmäßig, kann aber "in" den zweiten Teil gepumpt werden, indem Sie " $ to pump " wählen .$\{ \$ a^nb^n \mid n \ge 1 \} \cup \{ \$^kw \mid k\neq 1, w\in \{a,b\}^* \}$$\$$

(hinzugefügt) Natürlich kann dies für jedes L ⊆ { a , b } ∗ auf verallgemeinert werden . Manchmal hat die Formulierung den Stil "wenn ... dann ...": Wenn w mit einem einzelnen $ beginnt, hat sie die Form. Das finde ich persönlich weniger intuitiv.$\$L \cup \{ \$^k \mid k\neq 1 \} \cdot \{a,b\}^*$ $L\subseteq \{a,b\}^*$$w$$\$$

$\$\{a,b\}^*$