0
$\begingroup$

this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it to them. eg it is known that CFLs are not closed under intersection but thats not the immediate answer.) a proof is ok but also looking for ref(s) if known. analysis of nontrivial special cases also might be interesting. also a single non empty/non trivial example case has not been given so far (eg plz exclude both languages regular languages).

let $L_1, L_2$ be CFLs and $L=L_1 \cap L_2$ is known to be a CFL. is there an algorithm for constructing $L$?

$\endgroup$
6
$\begingroup$

It's well-known you can present computation history of a Turing machine as an intersection of two CFLs. Take a deterministic Turing machine $M$ and force it to reject everything except possibly the empty word. The set of computation histories is either empty (if $M$ rejects the empty word), or a singleton (if there's an accepting computation for the empty word), and if there was an algorithm for your problem, you could tell those cases apart.

$\endgroup$

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.