<p>By <a href="http://en.wikipedia.org/wiki/Context-free_grammar#Being_in_a_lower_level_of_the_Chomsky_hierarchy">Wikipedia</a> it is undecidable.</p>

CC BY-SA 3.0
2012-02-02T19:14:21.807Z
Fair enough; I guess I only looked at the page for CFLs and not CFGs. Still, the page you cite doesn't give any references for that claim, and even a more directed search in Sipser (using the sections in the "further reading" citations and a better index term) doesn't yield anything. Closest it has is "does this *TM* define a regular language", which falls right out of Rice's thm.
EvanED
CC BY-SA 3.0
2012-02-02T19:37:13.050Z
It's a consequence of Greibach's Theorem, see last pages here: http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf
Shir
CC BY-SA 3.0
2012-02-02T21:34:26.303Z
I found a reference to include in the Wikipedia article. (The source Shir posted looks better than the one I found, in the sense that it justifies the claim of undecidability rather than just stating it, but unfortunately it doesn't seem to be published yet.)
David Eppstein
CC BY-SA 3.0
2012-02-02T22:59:17.680Z
If the alphabet is unary it is decidable. ;)
Zach Langley
CC BY-SA 3.0
2012-02-02T23:35:25.983Z
@David, see my comment below the question for a published reference.
Kaveh
CC BY-SA 3.0
2013-12-30T14:03:14.547Z
Is the "regularity" of a context-free grammar recognizable or co-recognizable?
willeM_ Van Onsem
CC BY-SA 3.0
2012-02-02T18:55:30.997Z
2012-02-02T19:11:07.397Z
2012-02-02T19:11:07.397Z
Shir
<p>Is the decidablity of the following question known?</p>

<p><em>Given a CFG</em> G, <em>is</em> L(G) <em>regular?</em></p>

<p>I've seen a bunch of decidability results in the world of CFLs, but I don't think I've ever seen this one, and can't find anything about it.</p>

CC BY-SA 3.0
2012-02-02T23:33:53.850Z
See Hopcroft and Ullman, 1979, page 281.
Kaveh
<reference-request><fl.formal-languages>
Decidability of "does this CFG define a regular language"
EvanED
# Decidability of "does this CFG define a regular language"

(Asked by: username_0 on 2012-02-02)

Is the decidablity of the following question known?

*Given a CFG* G, *is* L(G) *regular?*

I've seen a bunch of decidability results in the world of CFLs, but I don't think I've ever seen this one, and can't find anything about it.

**Tags:** reference-request, fl.formal-languages

> **Comments:**
> **username_1**: See Hopcroft and Ullman, 1979, page 281.  

---

## 1 answers

### Answer by username_2 on 2012-02-02. Score: 5 | Accepted answer

By [Wikipedia](http://en.wikipedia.org/wiki/Context-free_grammar#Being_in_a_lower_level_of_the_Chomsky_hierarchy) it is undecidable.

> **Comments:**
> **username_0**: Fair enough; I guess I only looked at the page for CFLs and not CFGs. Still, the page you cite doesn't give any references for that claim, and even a more directed search in Sipser (using the sections in the "further reading" citations and a better index term) doesn't yield anything. Closest it has is "does this *TM* define a regular language", which falls right out of Rice's thm.  
> **username_2**: It's a consequence of Greibach's Theorem, see last pages here: http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf  
> **username_3**: I found a reference to include in the Wikipedia article. (The source username_2 posted looks better than the one I found, in the sense that it justifies the claim of undecidability rather than just stating it, but unfortunately it doesn't seem to be published yet.)  
> **username_4**: If the alphabet is unary it is decidable. ;)  
> **username_1**: @David, see my comment below the question for a published reference.  
> **username_5**: Is the "regularity" of a context-free grammar recognizable or co-recognizable?  

---

