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