将正规文法转化为正规式

本文主要是介绍将正规文法转化为正规式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

将正规文法转化为正规式有以下几个规则：

通过一道例题来讲解：

①A-->aC|bA

②C-->bD

③D-->aC|bD|

(1)首先将②带入③（不能将自身带入自身例如D-->aC|bD|,文法中带D，不能带入D）

D=abD|bD|=（ab|b）D | ，所以对应规则2(A-->xA|y),其中"(ab|b)"对应的是x，y对应的是

所以④D=x*y=(ab|b)*=(ab|b)*

(2)继续将②带入①:

⑤A=abD|bA

(3)将④带入⑤：

A=ab（ab|b）*|bA = bA|ab(ab|b)*，同样对应规则2，得到A=b*ab(ab|b)*

所以最后的结果为

A=b*ab(ab|b)*

C=bD

D=(ab|b)*

再来一道例题： 

 S→aA|a

 A→aA|dA|a|d

解如下： 

S = aA|a                

A = (aA|dA)|(a|d)=(a|d)A|(a|d)

由规则二: A = (a|d)*(a|d)

代入得: S = a(a|d)*(a|d)|a = a(a|d)*(a|d)|ε= a(a|d)*

 注：这里(ald)(ald)和(ald)是等价的，因为它们都表示任意多个(a或d)的组合。

这篇关于将正规文法转化为正规式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---