# Novel proof of pumping lemma for regular languages

Let $\mathcal{L}$ be the family of all languages over $\Sigma$ satisfying the pumping property of regular languages. Namely: for each $L\in\mathcal{L}$, there is an $N\in\mathbb{N}$ s.t. every word $w\in L$, $|w|> N$ can be written in the form $w=xyz$ where: 1. $|y|>0$, 2. $|xy|\le N$, 3. $xy^i z\in L$ for all $i\ge 0$.

It is a simple exercise to prove that $\mathcal{L}$ contains the singleton languages $L=\{\sigma\}$, $\sigma\in\Sigma$, and is closed under union, concatenation, and Kleene star. It is likewise well-known that the family of regular languages is the smallest one that contains the singletons and is closed under union, concatenation, and Kleene star. Conclusion: the regular languages satisfy the pumping property.

Question: has anyone seen this proof in the literature?  Proposed by D. Berend.

## 1 Answer

Essentially the same argument is made by Andries P.J. van der Walt (1976, Lemma 2.3 and Example 2.9) for the variant of the pumping lemma where $N$ letters are marked and all three of $x$, $y$, $z$ must contain marked letters. See also Autebert, Boasson, and Cousineau (1978) for more properties of abstract families of languages satisfying this variant of the pumping lemma.