# 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 ).

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.

 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$ ?" Apr 24 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. Apr 26 at 15:10
• For example, I have found a paper  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.  Tomoyuki Yamakami. Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas. Apr 26 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. Apr 23 at 7:48