16

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.

mhum
  • 3,382
  • 1
  • 21
  • 22
Aryeh
  • 10,494
  • 1
  • 27
  • 51

1 Answers1

15

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.

Sylvain
  • 3,374
  • 26
  • 22