4
$\begingroup$

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)

Improve this question
$\endgroup$
3
  • $\begingroup$ 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$ ?" $\endgroup$
    – Marzio De Biasi
    Commented Apr 24, 2023 at 21:50
  • $\begingroup$ 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. $\endgroup$
    – QMath
    Commented Apr 26, 2023 at 15:10
  • $\begingroup$ 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. $\endgroup$
    – QMath
    Commented Apr 26, 2023 at 15:35

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Apr 23, 2023 at 7:48
  • $\begingroup$ A shrinking lemma for indexed languages: doi.org/10.1016/0304-3975(96)00244-7 $\endgroup$
    – Hermann Gruber
    Commented Apr 23, 2023 at 15:08
  • $\begingroup$ Here is the pumping lemma: ems.press/journals/prims/articles/2632 . $\endgroup$
    – Emil Jeřábek
    Commented Apr 23, 2023 at 15:21
  • $\begingroup$ @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. $\endgroup$
    – domotorp
    Commented Apr 23, 2023 at 16:40
  • 1
    $\begingroup$ 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? $\endgroup$
    – Emil Jeřábek
    Commented Apr 23, 2023 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.