如何确定上下文无关语法是否描述了常规语言？

Question

给定任意上下文无关语法，我如何检查它是否描述了常规语言？

我不是在寻找考试“技巧”。我正在寻找一种可以编写代码的万无一失的机械测试。

如果有帮助的话，这里是我可能会收到作为输入的 CFG 示例。具体来说，请注意，答案一定比仅仅寻找左递归或右递归复杂得多，因为另一种类型的递归的存在并不自动意味着语法是不规则的。

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:

Answer 1

不存在这样的机械过程，因为确定CFG是否定义正则语言的问题是不可判定的。

这个结果是Greibach 定理的简单应用。