Языки, которые удовлетворяют лемме прокачки, но не являются регулярными?

Учитывая регулярный язык , легко доказать, что существует постоянная N такая, что σ ∈ L , причем | σ | ≥ N существуют строки α , β и γ такие, что | α β | ≤ N и | β | ≠ & epsi ; и для всех к это & alpha ; & beta ; к & gamma ∈ $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$, Широко утверждается, что обратное неверно, но я не видел четкого примера. Какие-либо предложения? Ясно, что доказательство того, что оскорбительный язык не является регулярным, должно использовать более сильные методы, чем типичное «не удовлетворяет насосной лемме». Я был бы заинтересован в простых примерах, чтобы представить во вводных классах формальных языков.

Язык представляется простым. Вторая часть обычная (и прокачиваемая). Первая часть нерегулярна, но ее можно «накачать» во вторую, выбрав $ для прокачки.$\{ \$ a^nb^n \mid n \ge 1 \} \cup \{ \$^kw \mid k\neq 1, w\in \{a,b\}^* \}$$\$$

(добавлено) Конечно, это можно обобщить на для любого L ⊆ { a , b } ∗ . Иногда формулировка выполнена в стиле «если ... тогда ...»: если w начинается с одного $, то она имеет форму. Это лично я нахожу менее интуитивным.$\$L \cup \{ \$^k \mid k\neq 1 \} \cdot \{a,b\}^*$ $L\subseteq \{a,b\}^*$$w$$\$$

Как отмечает @vonbrand, (возможно) нерегулярная часть языка изолируется путем пересечения с . Это может быть проверено отдельно с использованием леммы прокачки, если это необходимо.$\$\{a,b\}^*$