如何确定上下文无关的语法是否描述了常规语言? [英] 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.

如果有帮助，这是我可能会收到的CFG示例.具体来说，请注意，答案必须比查找左或右递归复杂得多，因为存在另一种递归并不自动表示语法是不规则的.

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:

推荐答案

没有这样的机械过程，因为确定CFG是否定义常规语言的问题尚不确定.

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

此结果是 Greibach's Thereom 的简单应用.

这篇关于如何确定上下文无关的语法是否描述了常规语言?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！