<p>Essentially the same argument is made by <a href="http://dx.doi.org/10.1016/S0019-9958(76)90083-8">Andries P.J. van der Walt (1976, Lemma 2.3 and Example 2.9)</a> 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 <a href="http://dx.doi.org/10.1016/S0019-9958(78)90365-0">Autebert, Boasson, and Cousineau (1978)</a> for more properties of abstract families of languages satisfying this variant of the pumping lemma.</p>

CC BY-SA 3.0
2016-04-01T23:07:06.677Z
2016-04-01T23:07:06.677Z
Sylvain
<p>Let $\mathcal{L}$ be the family of all languages over $\Sigma$ satisfying the <i>pumping property</i> 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|&gt; N$ can be written in the form
$ w=xyz$ where:
1. $|y|&gt;0$,
2. $|xy|\le N$,
3. $xy^i z\in L$ for all $i\ge 0$.</p>

<p>It is a simple exercise[1] 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.</p>

<p>Question: has anyone seen this proof in the literature?
[1] Proposed by D. Berend.</p>

<reference-request><fl.formal-languages><automata-theory>
Novel proof of pumping lemma for regular languages
Aryeh
# Novel proof of pumping lemma for regular languages

(Asked by: username_0 on 2016-03-31)

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[1] 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?
[1] Proposed by D. Berend.

**Tags:** reference-request, fl.formal-languages, automata-theory

---

## 1 answers

### Answer by username_1 on 2016-04-01. Score: 15 | Accepted answer

Essentially the same argument is made by [Andries P.J. van der Walt (1976, Lemma 2.3 and Example 2.9)](http://dx.doi.org/10.1016/S0019-9958(76)90083-8) 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)](http://dx.doi.org/10.1016/S0019-9958(78)90365-0) for more properties of abstract families of languages satisfying this variant of the pumping lemma.


---

