2
$\begingroup$

I've searched for a long time, but cannot find this. Maybe it's an open problem, but it seems not that hard.

Let's say I have a context-free grammar, say in Chomsky normal form for definiteness. Is there an algorithm to check whether it generates a regular language?

Of course, some simple cases can be easily decided, but I want to know whether there is a general procedure. I also know that for general grammars it is undecidable. If it is an open problem, so be it, but I won't think it is just because I haven't been able to find the answer. :-)

$\endgroup$

1 Answer 1

4
$\begingroup$

The following theorems are proved in Jeffrey Shallit's A Second Course in Formal Languages and Automata Theory.

Theorem 6.6.6. It is undecidable whether, given a CFG $G$, $L(G)$ is regular.

Theorem 6.6.7. There exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you very much! Not only for answering my question (and the one I intended to ask afterwards, too:), but for opening to me a whole new world of "Sequel to Formal Languages". :-) $\endgroup$
    – Veky
    Mar 15, 2017 at 19:54
  • $\begingroup$ Thanks a lot Fabio for the reference. So regularity of languages given by contex-free grammars is not decidable. Is it known that it is not even recursively enumerable? $\endgroup$
    – phs
    Sep 1, 2022 at 8:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .