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

  • 1
    $\begingroup$ 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 $\endgroup$
    – Lamine
    Commented Jul 5, 2013 at 8:15
  • $\begingroup$ 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. $\endgroup$
    – Max
    Commented Apr 23, 2014 at 21:49
  • 1
    $\begingroup$ Well, Wikipedia 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. $\endgroup$
    – Boson
    Commented Jan 19, 2017 at 23:13
  • $\begingroup$ The Scott -- Rabin pumping lemma is very different from the pumping lemmas listed here. $\endgroup$
    – C.E.Sally
    Commented Jan 6, 2019 at 19:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.