如果我们知道CFG只生成常规语言,我们可以得到相应的正则表达式吗？

Question

我们知道,给定一个常规语法,我们有算法来获得它的正则表达式.

但是如果给定的语法是无上下文语法(但它只生成常规语言),就像

S->aAb


A->bB


B->cB|d


S->aAb


A->bB


B->cB|d


S->aAb


A->bB


B->cB|d


S->aAb


A->bB


B->cB|d


是否有任何现有算法可以获得正则表达式？

谢谢!

Answer 1

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

因此，当已知 CFG 生成正则语言时，要么其语言已知（因此可以直接转换为 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 是两个不相交线性文法的串联。连接两个表达式作为最终表达式。Union 的逻辑类似。