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$
$\endgroup$
3
-
$\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 DraegerOct 5, 2018 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$– denidareOct 5, 2018 at 17:50
-
$\begingroup$ Related: stackoverflow.com/q/4134695/5376789 $\endgroup$– xskxzrOct 6, 2018 at 14:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
