Języki, które spełniają lemat pompowania, ale nie są regularne?

Biorąc pod uwagę regularny język , łatwo jest udowodnić, że istnieje stała N, taka jak σ ∈ L , z | σ | ≥ N istnieją łańcuchy α , β i γ takie, że | α β | ≤ N i | β | ≠ ϵ i dla wszystkich k jest to α β k γ ∈ $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$. Powszechnie stwierdza się, że odwrotność nie jest prawdą, ale nie widziałem żadnego wyraźnego przykładu. Jakieś sugestie? Najwyraźniej dowód na to, że obraźliwy język nie jest regularny, wymaga użycia silniejszych metod niż typowe „nie zaspokaja pompującego lematu”. Byłbym zainteresowany prostymi przykładami, do przedstawienia na wstępnych zajęciach z języków formalnych.

Język wydaje się prosty. Druga część jest regularna (i może być pompowana). Pierwsza część jest nieregularna, ale można ją „wpompować” do drugiej, wybierając $ do pompowania.$\{ \$ a^nb^n \mid n \ge 1 \} \cup \{ \$^kw \mid k\neq 1, w\in \{a,b\}^* \}$$\$$

(dodano) Oczywiście można to uogólnić do dla dowolnego L ⊆ { a , b } ∗ . Czasami sformułowanie jest w stylu „jeśli ... to ...”: jeśli w zaczyna się od pojedynczego $, to ma formę. Że osobiście uważam mniej intuicyjne.$\$L \cup \{ \$^k \mid k\neq 1 \} \cdot \{a,b\}^*$ $L\subseteq \{a,b\}^*$$w$$\$$

Jak zauważył @vonbrand (prawdopodobnie) nieregularna część języka jest izolowana przez przecięcie z . W razie potrzeby można to osobno przetestować za pomocą lematu pompującego.$\$\{a,b\}^*$