Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why?

I think it's undecidable but can't find any undecidable problem to reduce it to.

  • $\begingroup$ This is not really a research-level question and would be a better fit at cs.se. Here's a hint, however: The intersection of a context-free and a regular language is context-free, and emptiness of a context-free language is decidable. Can you take it from there? $\endgroup$ – Klaus Draeger Oct 5 '18 at 17:40
  • $\begingroup$ @KlausDraeger Ah, I'm sorry - I confused CS.se with cstheory. Also thanks for the hint, I think I got it now. $\endgroup$ – denidare Oct 5 '18 at 17:50
  • $\begingroup$ Related: stackoverflow.com/q/4134695/5376789 $\endgroup$ – xskxzr Oct 6 '18 at 14:31

Yes it is decidable.
We can construct a total Turing machine M that on input $G$ (where G is a CFG) checks whether it generates at least one string in $0^*1^*$.
Let $G_1$ be a regular language such that $L(G_1)=0^*1^*$.
Note that the intersection of CFL and a regular language is indeed a CFL. And hence a CFG for the intersection of $G$ and $G_1$ can be constructed. Call the constructed CFG $G'$. Also, the emptiness problem for CFG is decidable and hence just check the emptiness of the constructed CFG $G'$.
If it's empty, G doesn't generate any string in $0^*1^*$; and likewise if it's not empty.

| cite | improve this answer | |

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.