给定一个任意的无上下文语法，我如何检查它是否描述了常规语言？
我不是在寻找考试“技巧” . 我正在寻找一个可以编码的万无一失的机械测试 .
如果它有帮助，这是我作为输入可能会收到的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:
没有这样的机械程序，因为确定CFG是否定义常规语言的问题是不可判定的 .
这个结果是Greibach's Thereom的简单应用 .
1 回答
没有这样的机械程序，因为确定CFG是否定义常规语言的问题是不可判定的 .
这个结果是Greibach's Thereom的简单应用 .