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)

  • $\begingroup$ Hint: the intersection of a CFL and a regular language is a CFL, but the complement of a CFL is not necessarily a CFL. $\endgroup$
    – Nathaniel
    Apr 16 at 3:03
  • $\begingroup$ @Nathaniel Is it because we then have a PDA that can halt and tell us if it belongs to L, whereas the other one, can I construct a reduction from "is L everything" to "is L complement intersect R empty", where L is everything iff L complement intersect R empty? $\endgroup$ Apr 16 at 23:05

Your Answer

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

Browse other questions tagged or ask your own question.