Des langues qui satisfont au lemme de pompage mais qui ne sont pas régulières?

Étant donné un langage régulier , il est facile de prouver qu'il existe une constante telle que , avec il existe des chaînes , et telles que et , et pour tout c'est$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$. Il est largement dit que l'inverse n'est pas vrai, mais je n'ai vu aucun exemple clair. Aucune suggestion? Il est clair que la preuve que le langage offensant n'est pas régulier doit utiliser des méthodes plus fortes que le typique "ne satisfait pas le lemme de pompage". Je serais intéressé par des exemples simples, à présenter dans des cours d'introduction aux langues formelles.

La langue semble être simple. La deuxième partie est régulière (et peut être pompée). La première partie n'est pas régulière, mais peut être pompée "dans" la deuxième partie en choisissant $ à pomper.$\{ \$ a^nb^n \mid n \ge 1 \} \cup \{ \$^kw \mid k\neq 1, w\in \{a,b\}^* \}$$\$$

(ajouté) Bien sûr, cela peut être généralisé à pour tout L ⊆ { a , b } ∗ . Parfois la formulation est dans le style "si ... alors ...": si w commence par un seul $ alors c'est de la forme. Que je trouve personnellement moins intuitif.$\$L \cup \{ \$^k \mid k\neq 1 \} \cdot \{a,b\}^*$ $L\subseteq \{a,b\}^*$$w$$\$$

Comme l'a noté @vonbrand, la partie (éventuellement) non régulière du langage est isolée en coupant . Cela peut être testé séparément en utilisant le lemme de pompage si nécessaire.$\$\{a,b\}^*$