# 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?

## closed as off-topic by Kaveh, R B, Kristoffer Arnsfelt Hansen, Ryan Williams, Lev Reyzin♦Apr 3 '15 at 16:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, R B, Kristoffer Arnsfelt Hansen, Ryan Williams, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

• 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. – J.-E. Pin Mar 12 '15 at 7:51
• I think this is a pretty interesting (research level) question. Thanks for asking. :) – Michael Wehar Mar 13 '15 at 8:27
• @RB Indeed, undecidability follows directly from Greibach's Theorem. Thanks! – Petar Tsankov 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. – sdcvvc Mar 2 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/… – Sam Jones Mar 14 '15 at 15:54