将正规文法转化为正规式

2023-12-29 06:38:59

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

通过一道例题来讲解:

①A-->aC|bA

②C-->bD

③D-->aC|bD|\varepsilon

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

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

所以④D=x*y=(ab|b)*\varepsilon=(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)的组合。

文章来源:https://blog.csdn.net/weixin_69884785/article/details/135272569
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。