# Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?

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.

• 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? – Klaus Draeger Oct 5 '18 at 17:40
• @KlausDraeger Ah, I'm sorry - I confused CS.se with cstheory. Also thanks for the hint, I think I got it now. – denidare Oct 5 '18 at 17:50
• – xskxzr Oct 6 '18 at 14:31

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.