<p>The language <span class="math-container">$L_t=\{a_1^na_2^n\dots a_t^n:n\ge 0, a_i=a$</span> for odd <span class="math-container">$i$</span> and <span class="math-container">$a_i=b$</span> for even <span class="math-container">$i\}$</span> is the intersection of two CFL's, even <span class="math-container">$\cup_t~L_t$</span> is, and it is hard to imagine what kind of pumping lemma could hold for them.</p>

CC BY-SA 4.0
2023-04-23T07:48:24.027Z
Each $L_t$ is an indexed language, and so is $\bigcup_tL_t$. There is a pumping lemma for indexed languages, but I do not know the details.
Emil Jeřábek
CC BY-SA 4.0
2023-04-23T15:08:29.067Z
A shrinking lemma for indexed languages: https://doi.org/10.1016/0304-3975(96)00244-7
Hermann Gruber
CC BY-SA 4.0
2023-04-23T15:21:01.360Z
Here is the pumping lemma: https://ems.press/journals/prims/articles/2632 .
Emil Jeřábek
CC BY-SA 4.0
2023-04-23T16:40:46.440Z
@Emil I looked at the linked paper, but it is quite challenging to extract the pumping lemma from it without wading through all the definitions. If you could convert your comment into an answer, then it would be of interest to most of us.
domotorp
CC BY-SA 4.0
2023-04-23T17:05:24.387Z
I am not familiar with this stuff, as I already wrote, and as far as I can see, it does not answer the original question. Or is it true that arbitrary intersections of context-free languages are indexed languages?
Emil Jeřábek
CC BY-SA 4.0
2023-04-26T15:13:18.133Z
No, at least not effectively. You can encode the Halting problem into the intersection of two context free languages, so that it is nonempty if the machine halts iirc. The emptiness problem for indexed grammars is decidable.
Hermann Gruber
CC BY-SA 4.0
2023-04-23T04:16:45.707Z
2023-04-23T04:16:45.707Z
domotorp
<p>The class of context-free languages is not closed under intersection. For example, the language <span class="math-container">$L=\{a^nb^nc^n : n\geq 0\}$</span> is not context-free, but it is an intersection of two context-free languages. Similarly, one can construct languages that are intersections of <span class="math-container">$k$</span> CFL but not an intersection of <span class="math-container">$k-1$</span> CFL (see [1]).</p>
<p><strong>Question.</strong> Is there a pumping lemma for the intersection of two or finitely many context-free languages?</p>
<p>Also, I am wondering if there is an automaton model for the intersection of two or finitely many CFL.</p>
<p>[1] Liu, L.Y., Weiner, P.: An infinite hierarchy of intersections of context-free languages. Math. Syst. Theory 7, 185–192 (1973)</p>

CC BY-SA 4.0
2023-04-24T21:50:03.017Z
Sorry for the clarification request, but what do you exactly mean with "is there a pumping lemma for the intersection of two CFLs?" given that such intersection can be a non CF language? Do you mean something like: "given $L_1, L_2$ CFLs, if condition C is met (for example the condition C could be *the intersection is still CF*?!?) then if a string $x$ belongs to the intersection $L_1 \cap L_2$, we can pump it in some way and the result is still in $L_1 \cap L_2$ ?"
Marzio De Biasi
CC BY-SA 4.0
2023-04-26T15:10:12.773Z
Basically, yes. But the condition C should be weak enough so that one can easily apply the lemma to show that certain languages are not an intersection of two CFL.
QMath
CC BY-SA 4.0
2023-04-26T15:35:01.740Z
For example, I have found a paper [2] where there is some kind of a pumping lemma for the union of deterministic CFLs. The lemma looks complicated for me, but it allows to prove that certain languages are not an intersection of two deterministic CFLs. 

[2] Tomoyuki Yamakami. Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas.
QMath
<automata-theory><context-free>
Pumping lemma for CFL intersection
QMath
# Pumping lemma for CFL intersection

(Asked by: username_0 on 2023-04-22)

The class of context-free languages is not closed under intersection. For example, the language $L=\{a^nb^nc^n : n\geq 0\}$ is not context-free, but it is an intersection of two context-free languages. Similarly, one can construct languages that are intersections of $k$ CFL but not an intersection of $k-1$ CFL (see [1]).

**Question.** Is there a pumping lemma for the intersection of two or finitely many context-free languages?

Also, I am wondering if there is an automaton model for the intersection of two or finitely many CFL.

[1] Liu, L.Y., Weiner, P.: An infinite hierarchy of intersections of context-free languages. Math. Syst. Theory 7, 185–192 (1973)

**Tags:** automata-theory, context-free

> **Comments:**
> **username_1**: Sorry for the clarification request, but what do you exactly mean with "is there a pumping lemma for the intersection of two CFLs?" given that such intersection can be a non CF language? Do you mean something like: "given $L_1, L_2$ CFLs, if condition C is met (for example the condition C could be *the intersection is still CF*?!?) then if a string $x$ belongs to the intersection $L_1 \cap L_2$, we can pump it in some way and the result is still in $L_1 \cap L_2$ ?"  
> **username_0**: Basically, yes. But the condition C should be weak enough so that one can easily apply the lemma to show that certain languages are not an intersection of two CFL.  
> **username_0**: For example, I have found a paper [2] where there is some kind of a pumping lemma for the union of deterministic CFLs. The lemma looks complicated for me, but it allows to prove that certain languages are not an intersection of two deterministic CFLs.   [2] Tomoyuki Yamakami. Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas.  

---

## 1 answers

### Answer by username_2 on 2023-04-23. Score: 1

The language $L\_t=\{a\_1^na\_2^n\dots a\_t^n:n\ge 0, a\_i=a$ for odd $i$ and $a\_i=b$ for even $i\}$ is the intersection of two CFL's, even $\cup\_t~L\_t$ is, and it is hard to imagine what kind of pumping lemma could hold for them.

> **Comments:**
> **username_3**: Each $L_t$ is an indexed language, and so is $\bigcup_tL_t$. There is a pumping lemma for indexed languages, but I do not know the details.  
> **username_4**: A shrinking lemma for indexed languages: https://doi.org/10.1016/0304-3975(96)00244-7  
> **username_3**: Here is the pumping lemma: https://ems.press/journals/prims/articles/2632 .  
> **username_2**: @Emil I looked at the linked paper, but it is quite challenging to extract the pumping lemma from it without wading through all the definitions. If you could convert your comment into an answer, then it would be of interest to most of us.  
> **username_3**: I am not familiar with this stuff, as I already wrote, and as far as I can see, it does not answer the original question. Or is it true that arbitrary intersections of context-free languages are indexed languages?  
> **username_4**: No, at least not effectively. You can encode the Halting problem into the intersection of two context free languages, so that it is nonempty if the machine halts iirc. The emptiness problem for indexed grammars is decidable.  

---

