1)"Given a CFL L and a regular language R, is the intersection of L and R an empty set?" decidable?
2)What if we replace L with the complement of L?
Either 1 or 2 is decidable and the other is not.
For the one that is decidable, give an algorithm. For the other, give an undecidability proof.
Intuitively, i think that 1 is decidable and 2 is undecidable.
However, I don't have a concrete reasoning behind it.
Can anyone explain why or why not this is the answer?
(PS this is not for an assignment, this is a practice final question)