2
$\begingroup$

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?

$\endgroup$

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.

  • 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$ – Michael Wehar Mar 13 '15 at 8:27
  • $\begingroup$ @RB Indeed, undecidability follows directly from Greibach's Theorem. Thanks! $\endgroup$ – Petar Tsankov 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 at 21:14
9
$\begingroup$

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.

$\endgroup$
  • 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.