2
$\begingroup$

Is the following problem decidable?

Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$?

It is given that the following problem is undecidable

Given a context-free grammar G, is $ L(G) = \Sigma ^*$ ? $\ (1)$

and this problem decidable

Given a context-free grammar G, is $ L(G) = \emptyset $ ? $\ \ \ (2)$

My thought is this:

$L(G) \subseteq L(R)$ is the same as $ L(G) \cap \overline{L(R)} = \emptyset $. So, since regular languages are closed under complement, and the intersection of a $CFL$ with a $RL$ is a $CFL$, $L(G) \cap \overline{L(R)}$ is a $CFL$. Now, $(2)$ is decidable, so if we can create a context-free grammar for $L(G) \cap \overline{L(R)}$ and give it as input to a decider for $(2)$ we have decided our initial problem.

Is my thought correct? And if yes, how can create such a grammar?

$\endgroup$
3
$\begingroup$

Yes, your thought is correct. The only missing part, as you pointed out, is whether or how we can create a CFL algorithmically for the intersection of a CFL with a RL.

If you take a close look at any proof for the fact that the intersection of a CFL with a RL is a CFL, you will find that the proof is constructive or can be made to be constructive easily, giving that there is an algorithm to construct the CFL for a given PDA. Here "constructive" means the same as "algorithmic". It is just by convention or history, we tend to use the word "constructive" instead of "algorithmic" to describe a proof.

You can check your textbook, or this and this.

Exercise. Is the following problem decidable?

Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \supseteq L(R)$?

$\endgroup$
  • 1
    $\begingroup$ Thank you for the answer! About the exercise I would say no, it is not decidable. If it were decidable, given the regular expression $ (a \cup b)^* $, we would be able to determine if $ \Sigma ^* \subseteq L(G) \Leftrightarrow L(G) = \Sigma ^* $ which is undecidable. So we get a contradiction, thus the initial assumption is false. $\endgroup$ – Da Mike Jun 19 at 21:52

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.