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
    Jul 5 '13 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
    Apr 23 '14 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
    Jan 19 '17 at 23:13
  • $\begingroup$ The Scott -- Rabin pumping lemma is very different from the pumping lemmas listed here. $\endgroup$
    – C.E.Sally
    Jan 6 '19 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.