-2

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.

Janoma
  • 1,406
  • 11
  • 27
EvanED
  • 131
  • 2

1 Answers1

5

By Wikipedia it is undecidable.

Shir
  • 721
  • 4
  • 11
  • 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 Feb 02 '12 at 19:14
  • 9
    It's a consequence of Greibach's Theorem, see last pages here: http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf – Shir Feb 02 '12 at 19:37
  • 2
    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 Feb 02 '12 at 21:34
  • 1
    If the alphabet is unary it is decidable. ;) – Zach Langley Feb 02 '12 at 22:59
  • @David, see my comment below the question for a published reference. – Kaveh Feb 02 '12 at 23:35
  • Is the "regularity" of a context-free grammar recognizable or co-recognizable? – willeM_ Van Onsem Dec 30 '13 at 14:03