13
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 15:53

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

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

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