regex - 如果我们知道一个CFG只生成正则语言，那么我们能得到对应的正则表达式吗？

Question

众所周知，给定一个正则语法，我们有算法来获取它的正则表达式。

但是如果给定的语法是上下文无关语法(但它只生成常规语言)，例如




S->aAb <br/>


A->bB <br/>


B->cB|d <br/>


有没有现成的算法可以得到通用的正则表达式？

谢谢!

Answer 1

从最一般的意义上来说，没有解决方案。确定 CFG 是否正则的问题是不可判定的(Greibach 定理，http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf 的最后 3 页)如果我们可以将 CFG 转换为正则表达式，我们可以在任何语法上使用该算法，并使用其成功/失败来确定是否语言是有规律的。

因此，当已知 CFG 生成正则语言时，要么其语言已知(因此可以直接转换为正则表达式)，要么存在可以利用的语法的某些属性。每个属性都有自己的转换为正则表达式的算法。

例如，如果语法为 right linear ，每个产生式都是 A->bC 或 A->a 的形式。这可以转换为 NFA，其中:

1) 每个非终结符都有一个状态，外加一个接受状态。

2)起始符号S为起始状态。

3) A->bC 是输入 b 上从 A 到 B 的转换

4) A->a 是从 A 到输入 a 的接受状态的转换。

然后可以通过状态消除将该 NFA 转换为正则表达式(http://www.math.uaa.alaska.edu/~afkjm/cs351/handouts/regular-expressions.pdf 的第 5-8 页)。左线性语法的类似过程将交换开始和接受状态。

除此之外，我们还可以利用常规语言的闭包属性。例如，问题中的语言不是线性的，但可以写成S->S'b，S'->aA。现在 S' 是右线性的，S 是两个不相交线性文法的串联。连接两个表达式作为最终表达式。 union 的逻辑类似。