<p>I'm looking to track down who discovered the following pumping lemmas for regular languages.
(where $p$ is the pumping constant.)</p>

<p>Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_1u_2v(\in \Sigma^*), w= u_1vu_2  \wedge |w| \geq p$<br>
$\rightarrow\exists xyz, v=xyz \wedge |xy| \leq p \wedge y \not = \epsilon \wedge \mathbf{u_1xy^*zu_2} \subset L$</p>

<p>Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_0u_1 \ldots u_p(\in \Sigma^*), w = u_0u_1 \ldots u_p$<br>
$\rightarrow \exists ij, 0 &lt; i \leq j &lt; p \wedge \mathbf{u_0u_1 \ldots u_{i-1}(u_iu_{i+1} \ldots u_j)^*u_{j+1}u_{j+2}\ldots u_p} \subset L$</p>

<p>Thank you</p>

CC BY-SA 3.0
2013-07-05T08:15:26.923Z
May be Yehoshua Bar-Hillel, Micha A. Perles et Eli Shamir, « On formal properties of simple phrase structure grammars », Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, vol. 14, 1961, p. 143-172
Lamine
CC BY-SA 3.0
2014-04-23T21:49:34.397Z
I've heard that that paper contains the pumping lemma for CFLs (which was for some time called the "Bar-Hillel lemma") but the pumping lemma for regular languages was already known. However, I've never actually seen the Bar-Hillel, et al. paper.
Max
CC BY-SA 3.0
2017-01-19T23:13:05.893Z
Well, [Wikipedia](https://en.wikipedia.org/w/index.php?title=Pumping_lemma_for_regular_languages&oldid=546220579) cites Scott and Rabin as the discoverers of the pumping lemma (and links to the paper). Let me add that this mention was already online when the question was asked.
Boson
CC BY-SA 4.0
2019-01-06T19:36:06.590Z
The Scott -- Rabin pumping lemma is very different from the pumping lemmas listed here.
C.E.Sally
<reference-request><fl.formal-languages><automata-theory><ho.history-overview><regular-language>
Providence of pumping lemmas for regular languages
C.E.Sally
# Providence of pumping lemmas for regular languages

(Asked by: username_0 on 2013-07-03)

I'm looking to track down who discovered the following pumping lemmas for regular languages.
(where $p$ is the pumping constant.)

Reg($L) \rightarrow \exists p\forall w(\in L) \forall u\_1u\_2v(\in \Sigma^\*), w= u\_1vu\_2 \wedge |w| \geq p$  
$\rightarrow\exists xyz, v=xyz \wedge |xy| \leq p \wedge y \not = \epsilon \wedge \mathbf{u\_1xy^\*zu\_2} \subset L$

Reg($L) \rightarrow \exists p\forall w(\in L) \forall u\_0u\_1 \ldots u\_p(\in \Sigma^\*), w = u\_0u\_1 \ldots u\_p$  
$\rightarrow \exists ij, 0 < i \leq j < p \wedge \mathbf{u\_0u\_1 \ldots u\_{i-1}(u\_iu\_{i+1} \ldots u\_j)^\*u\_{j+1}u\_{j+2}\ldots u\_p} \subset L$

Thank you

**Tags:** reference-request, fl.formal-languages, automata-theory, ho.history-overview, regular-language

> **Comments:**
> **username_1**: May be Yehoshua Bar-Hillel, Micha A. Perles et Eli Shamir, « On formal properties of simple phrase structure grammars », Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, vol. 14, 1961, p. 143-172  
> **username_2**: I've heard that that paper contains the pumping lemma for CFLs (which was for some time called the "Bar-Hillel lemma") but the pumping lemma for regular languages was already known. However, I've never actually seen the Bar-Hillel, et al. paper.  
> **username_3**: Well, [Wikipedia](https://en.wikipedia.org/w/index.php?title=Pumping_lemma_for_regular_languages&oldid=546220579) cites Scott and Rabin as the discoverers of the pumping lemma (and links to the paper). Let me add that this mention was already online when the question was asked.  
> **username_0**: The Scott -- Rabin pumping lemma is very different from the pumping lemmas listed here.  

---

## 0 answers

