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?

  • 3
    $\begingroup$ 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. $\endgroup$
    – R B
    Mar 12 '15 at 4:19
  • $\begingroup$ Not a research level question. $\endgroup$
    – J.-E. Pin
    Mar 12 '15 at 7:51
  • 1
    $\begingroup$ I think this is a pretty interesting (research level) question. Thanks for asking. :) $\endgroup$ Mar 13 '15 at 8:27
  • $\begingroup$ @RB Indeed, undecidability follows directly from Greibach's Theorem. Thanks! $\endgroup$ Mar 16 '15 at 13:01
  • $\begingroup$ @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. $\endgroup$
    – sdcvvc
    Mar 2 '19 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.

  • 1
    $\begingroup$ 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/… $\endgroup$
    – Sam Jones
    Mar 14 '15 at 15:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.