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

Question

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

但是如果给定的语法是上下文无关的语法（但它只生成常规语言），比如

S->aAb


A->bB


B->cB|d


是否有任何现有的算法可以得到一般的正则表达式？

谢谢！</p>

Answer 1

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

因此，相反，当已知 CFG 生成正则语言时，要么它的语言是已知的（因此可以直接转换为 RegEx），要么有一些语法的属性可以利用。每个属性都有自己的算法用于转换为 RegEx。

例如，如果语法是右线性的，那么每个产生式的形式都是 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 是两个不相交的线性文法的串联。连接两个表达式以获得最终表达式。联合的类似逻辑。