# Pumping lemma for CFL intersection

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)

• 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$ ?" Commented Apr 24, 2023 at 21:50
• 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. Commented Apr 26, 2023 at 15:10
• 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. Commented Apr 26, 2023 at 15:35

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.
• 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. Commented Apr 23, 2023 at 7:48