如果我们知道一个CFG仅产生普通的语言，我们可以得到相应的正则表达式？(If we know a C

我们知道，给定一个正规文法，我们的算法来获得它的正则表达式。

但是，如果给定的语法是上下文无关文法（但仅产生正规语言），如

S->aAb 
 A->bB 
 B->cB|d

S->aAb 
 A->bB 
 B->cB|d

S->aAb 
 A->bB 
 B->cB|d

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

谢谢！

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

因此，而不是，当CFG已知产生一个普通的语言，无论是它的语言是已知的（并因此直接转换为正则表达式），或有语法利用的某些属性。每个属性都有自己的算法转换为正则表达式。

例如，如果语法是正确的线性，每生产是形式A-> BC的或A->一个。这可以转换为NFA，其中：

1）为每一个非终端的状态，再加上一个接受状态。

2）开始符号S是开始状态。

3）A-> BC是从A到B上输入B的过渡

4）A-> a是从A到上输入的接受状态的转移。

此NFA然后可以经由状态消除（5-8页转换为正则表达式http://www.math.uaa.alaska.edu/~afkjm/cs351/handouts/regular-expressions.pdf ）。左线性文法类似的方法将有开始和接受状态交换。

除此之外，人们可以利用正规语言的封闭性。例如，在问题的语言不是线性的，但它可以被写为S-> S'B，S' - > AA。现在S”是右线性的，并且S是两个不相交的线性文法的串联。串接的最后表达两个表达式。同样的逻辑工会。