1
$\begingroup$

It is a well-known that it is undecidable in general whether an arbitrary context-free grammar generates a regular language. However, I could not find any results concerning the question whether this problem might be semi-decidable. Is there a definitive answer to this question, positive or negative?

$\endgroup$
2
$\begingroup$

There can't be an algorithm that takes a context-free grammar as input and

  • if the language it generates is regular, the algorithm outputs an equivalent regular grammar;
  • otherwise the algorithm diverges.

If we had such an algorithm, we could use it to determine whether a grammar generates all strings (a known undecidable problem), by running it in parallel with a search for something the grammar doesn't generate. (If the algorithm terminates, if it a simple problem to determine if the regular grammar generates everything).

This argument does not completely rule out that there might be an algorithm that simply says "yes, this grammar generates a regular language, but I won't tell you which". But it seems to make it intuitively unlikely.

$\endgroup$
  • $\begingroup$ Thanks Henning for you help (i granted you +1, but i don't have enough reputation to change the public score on your answer). $\endgroup$ – Raoul May 21 '18 at 15:23
  • $\begingroup$ However, your proof-sketch seems to reduce the problem to the question "is it semi-decidable whether a context-free grammar generates the universal language?", but maybe I missed a point. $\endgroup$ – Raoul May 21 '18 at 15:29
  • 1
    $\begingroup$ @Raoul: (a) It is well known to be decidable whether a regular grammar generates the universal language: Just convert to a DFA, minimize the DFA, and see if you get the one-state always-accepting automaton. (b) It is semi-decidable whether a CFG doesn't generate the universal language: Since you can check for each string whether it's generated by the grammar or not, just enumerate all strings until you find one not in the language. $\endgroup$ – Henning Makholm May 21 '18 at 15:34
  • $\begingroup$ Yay, that helped. Thank you so much! $\endgroup$ – Raoul May 21 '18 at 15:37
  • $\begingroup$ I think I can incorporate your help into my master-thesis and I will of course grant you attribution, if you'd like to. Please let me know if you have preferences on the form of attribution regarding calling you by your full name, homepage link or any academic work you performed on this topic. $\endgroup$ – Raoul May 21 '18 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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