<p>There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, <a href="https://link.springer.com/chapter/10.1007/BFb0025726" rel="noreferrer">here</a>, <a href="https://books.google.com/books?id=pFlgSZtLg4sC&amp;pg=PA270&amp;lpg=PA270&amp;dq=%22also+called+Bar-Hillel%27s+Lemma%22&amp;source=bl&amp;ots=WR2W-pHWYj&amp;sig=h0EspLMk-TG0D-N80XJrY0whf7M&amp;hl=en&amp;sa=X&amp;ved=0ahUKEwj66qf6x53UAhVGDMAKHT9dCr0Q6AEINjAC" rel="noreferrer">here</a>, and on the <a href="https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages" rel="noreferrer">Wikipedia page</a>). However, the first article to prove the result was only co-authored by Bar-Hillel:</p>

<p>Y. Bar-Hillel, M. Perles, E. Shamir. On formal properties of simple phrase structure grammars. <em>Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung</em>, <strong>14</strong>:143–172, 1961.</p>

<p>Is there a good reason the result is sometimes called Bar-Hillel's Lemma, or is it simply a mis-attribution?</p>

CC BY-SA 3.0
2017-06-03T17:09:43.990Z
For what it's worth, the [Wikipedia entry](https://en.wikipedia.org/wiki/Yehoshua_Bar-Hillel) for Bar-Hillel states the following: "In 1953, he founded a pioneering algebraic-computational linguistic group, and in 1961 **he contributed to the proof of the pumping lemma** for context-free languages (sometimes called the Bar-Hillel lemma)." (emphasis mine)
Clement C.
CC BY-SA 3.0
2017-06-04T07:17:15.150Z
There are some recent slides by Eli Shamir here (http://mps2016.labri.fr/archives/shamir.pptx) that include this paper. It's hard to know what words went along with the slides, but they do mention that Perles and Shamir were PhD students in math at the time, whereas Bar-Hillel was a professor who already had an established record in  algebraic linguistics (http://www.dtic.mil/dtic/tr/fulltext/u2/400604.pdf). This is just speculation, but perhaps the reason the lemma got attached to Bar-Hillel's name had to do with the asymmetric relationship of the three coauthors?
Noam Zeilberger
CC BY-SA 4.0
2019-04-04T07:49:09.573Z
Also, it happens sometimes that the authors disclose to which of them some lemma/theorem is due to, see for example the Lovasz Local Lemma from Erdős, Paul; Lovász, László: Problems and results on 3-chromatic hypergraphs and some related questions - in this case it was Erdos who wanted to make it clear that the lemma was entirely Lovasz's.
domotorp
<fl.formal-languages><context-free><ho.history-overview>
Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?
Vince Vatter
# Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?

(Asked by: username_0 on 2017-06-01)

There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, [here](https://link.springer.com/chapter/10.1007/BFb0025726), [here](https://books.google.com/books?id=pFlgSZtLg4sC&pg=PA270&lpg=PA270&dq=%22also+called+Bar-Hillel%27s+Lemma%22&source=bl&ots=WR2W-pHWYj&sig=h0EspLMk-TG0D-N80XJrY0whf7M&hl=en&sa=X&ved=0ahUKEwj66qf6x53UAhVGDMAKHT9dCr0Q6AEINjAC), and on the [Wikipedia page](https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages)). However, the first article to prove the result was only co-authored by Bar-Hillel:

Y. Bar-Hillel, M. Perles, E. Shamir. On formal properties of simple phrase structure grammars. *Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung*, **14**:143–172, 1961.

Is there a good reason the result is sometimes called Bar-Hillel's Lemma, or is it simply a mis-attribution?

**Tags:** fl.formal-languages, context-free, ho.history-overview

> **Comments:**
> **username_1**: For what it's worth, the [Wikipedia entry](https://en.wikipedia.org/wiki/Yehoshua_Bar-Hillel) for Bar-Hillel states the following: "In 1953, he founded a pioneering algebraic-computational linguistic group, and in 1961 **he contributed to the proof of the pumping lemma** for context-free languages (sometimes called the Bar-Hillel lemma)." (emphasis mine)  
> **username_2**: There are some recent slides by Eli Shamir here (http://mps2016.labri.fr/archives/shamir.pptx) that include this paper. It's hard to know what words went along with the slides, but they do mention that Perles and Shamir were PhD students in math at the time, whereas Bar-Hillel was a professor who already had an established record in  algebraic linguistics (http://www.dtic.mil/dtic/tr/fulltext/u2/400604.pdf). This is just speculation, but perhaps the reason the lemma got attached to Bar-Hillel's name had to do with the asymmetric relationship of the three coauthors?  
> **username_3**: Also, it happens sometimes that the authors disclose to which of them some lemma/theorem is due to, see for example the Lovasz Local Lemma from Erdős, Paul; Lovász, László: Problems and results on 3-chromatic hypergraphs and some related questions - in this case it was Erdos who wanted to make it clear that the lemma was entirely Lovasz's.  

---

## 0 answers

