1
$\begingroup$

I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the intersection?

𝐿∩𝑅=∅ and $\bar{𝐿}$∩𝑅=∅

This is what I think but I am not sure so any help is appreciated.

For 𝐿, I think this is decidable because intersection of a CFL and a regular language is a CFL so you can build CFG for it. However, it can also be undecidable as we can check membership for all elements in Σ∗ which can take forever so we don't know if there is going to be an element that'll be in this intersection.

As for $\bar{𝐿}$, this one I don't really know at all.

Please excuse me if I made mistakes or if my explanation was unclear. I am new to the topic and trying to wrap my head around it and any help is appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

The first one you have solved correctly. Emptiness of context-free languages is decidable.

For the second, we can rewrite $\bar L \cap R = \varnothing$ into $R\subseteq L$. This is undecidable (even for $R=\Sigma^*$).

$\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.