Apropois to Raphael's suggestion on Intersection of two NPDAs:

Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is context-free, can we (effectively) construct NPDA $A$ for $L$?

Any type of algorithm would be acceptable, but the more practical the better.

  • $\begingroup$ an example of such an L where neither L1/L2 are regular and the intersection is not empty might be helpful, does such an L exist? somewhat similar problems wrt NPDAs (testing emptiness of intersection, testing equality) are undecidable. suggest migrate/promote to tcs.se if no answer materializes $\endgroup$ – vzn Mar 27 '14 at 20:25
  • $\begingroup$ @vzn I believe I have a ~50 state example, I'll try to find someone that is more minimal $\endgroup$ – soandos Mar 28 '14 at 0:00
  • 1
    $\begingroup$ The set of strings "at least 1/3 1's" and "fewer than 2/3 1's" over the alphabet $\{0,1\}$ are both DCFLs, and their intersection is a CFL (and not a DCFL) $\endgroup$ – sjmc Apr 1 '14 at 18:07
  • $\begingroup$ @sjmc can you sketch out a proof? not obvious to me. will upvote if you post it as answer even though its not complete answer, its some progress $\endgroup$ – vzn Apr 5 '14 at 14:53
  • $\begingroup$ update this appears to be answered as undecidable at tcs.se based on that arbitrary TM computation can be expressed as the intersection of two CFLs. $\endgroup$ – vzn Apr 5 '14 at 15:53

I think this is possible for the subclass of CFLs that are permutation-invariant with a binary alphabet.

These correspond to type $\langle 1,1\rangle$ quantifier languages comparing the cardinalities of two sets. [1] characterizes such languages accepted by DPDA by the equivalent semilinear sets, and states at the end that quantifier languages accepted by NPDA are finite boolean combinations of such languages accepted by DPDA.

A theorem of van Benthem ([2]) says that pushdown automata accept type $\langle 1,1\rangle$ quantifiers definable in Presburger arithmetic (i.e. defined by semilinear sets). So, if you get two languages that are non-deterministic CFLs (using the first paper to know you have such examples), their intersection should also be a CFL by this theorem.

The semilinear set which is their intersection might be a bit difficult to compute... but, if you have that, [3] (pgs.11-12) give an algorithm for creating an NPDA accepting the language based on the generators of the corresponding semilinear set.

[1] Makoto Kanazawa. Monadic quantiers recognized by deterministic push- down automata. In Proceedings of the 19th Amsterdam Colloquium, pages 139-146, 2013.

[2] Johann van Benthem. Essays in Logical Semantics. Studies in Linguistics and Philosophy Volume 29, 1986, pp 151-176.

[3] Marcin Mostowski. Computational semantics for monadic quantiers. Journal of Applied Non-Classical Logics, 8(1-2):107-121, 1998.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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