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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.