# 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
Commented Mar 12, 2015 at 4:19
• Not a research level question. Commented Mar 12, 2015 at 7:51
• I think this is a pretty interesting (research level) question. Thanks for asking. :) Commented Mar 13, 2015 at 8:27
• @RB Indeed, undecidability follows directly from Greibach's Theorem. Thanks! Commented Mar 16, 2015 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. Commented Mar 2, 2019 at 21:14

Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages.

Regarding DCFL, I have two references (from Hopcroft+Ullman 79):

Regarding a procedure to get a regular version when possible, I have no suggestion.

• 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/… Commented Mar 14, 2015 at 15:54
• @SamJones Is that still true for deterministic CFLs? Commented Mar 28 at 4:36