Search code examples
grammarcontext-free-grammarregular-languagefinite-automataformal-languages

How to determine if a context-free grammar describes a regular language?

Given an arbitrary context-free grammar, how can I check whether it describes a regular language?

I'm not looking for exam "tricks". I'm looking for a foolproof mechanical test that I can code.

If it helps, here's an example of a CFG that I might receive as an input. Specifically, notice that the answer must be much more complicated than just looking for left- or right-recursion, since the presence of another type of recursion does not automatically imply the grammar is irregular.

S: A B C D X
A: A a
A:
B: b B
B:
C: c C c
C: c
D: D d D
D: d
X: x Y
X:
Y: y X
Y:
Solution

  • There is no such mechanical procedure because the problem of determining whether a CFG defines a regular language is undecidable.

    This result is a simple application of Greibach's Thereom.