# Deciding whether a context-free language is regular [closed]

Does anyone know whether the following decision problem is decidable:

Given a context-free language $L$, is $L$ regular?

Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone know an algorithm that takes as input a context-free grammar $G$ and outputs an equivalent regular grammar $G'$, i.e. $L(G) = L(G')$, if $L(G)$ is regular?

• You could either use Greibach Theorem to show it's undecidable, or just notice that universality is undecidable for CFGs, but is decidable for regular languages.
– R B
Mar 12 '15 at 4:19
• Not a research level question. Mar 12 '15 at 7:51
• I think this is a pretty interesting (research level) question. Thanks for asking. :) Mar 13 '15 at 8:27
• @RB Indeed, undecidability follows directly from Greibach's Theorem. Thanks! Mar 16 '15 at 13:01
• @RB I agree about Greibach's theorem, but I believe the two facts about universality are not enough. They can be used to show that it's not possible to convert a CFG to a regular language when possible, but this does not yet mean it's undecidable to merely decide whether a context-free language is regular. Mar 2 '19 at 21:14

• The procedure to get a regular grammar can't exist. Given a Turing machine $M$ one can construct a Context-free grammar whose language is either $\Sigma^{*}$ or $\Sigma^{*} - w$ depending on whether $M$ halts. These are both regular languages and so if we could exhibit a regular grammar we could decide the halting problem. The full proof is in Shallit's book amazon.co.uk/Second-Course-Formal-Languages-Automata/dp/… Mar 14 '15 at 15:54