将正规文法转化为正规式

简介: 将正规文法转化为正规式

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

通过一道例题来讲解:

①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)的组合。


目录
相关文章
|
7月前
|
Cloud Native 容器
ldif 数据转成正确的组织结构再探
ldif 数据转成正确的组织结构再探
|
25天前
|
算法
年和日转化为天干地支
年和日转化为天干地支
5 0
|
1月前
【全网最精简】一行代码解决千万位以上的数字格式化为银行金额数字格式/货币格式(如:¥1,000,000,000.00)
【全网最精简】一行代码解决千万位以上的数字格式化为银行金额数字格式/货币格式(如:¥1,000,000,000.00)
|
10月前
数字的转化规则?
转换规则:不管你要转的数据是什么,都是一位一位的去检测,如果第一位可以转成数字,就转,依次往后看每一位,直到碰到不能转或者转完为止,如果转不成就直接NaN
|
11月前
如何用正则表达式判断手机号格式正不正确
如何用正则表达式判断手机号格式正不正确
113 0
|
12月前
|
存储 安全 测试技术
数字藏品铸造交易平台开发源码规则解析
数字藏品铸造交易平台开发源码规则解析
|
存储 C#
【c#入门杂选】-显性转换,和隐形转换
【c#入门杂选】-显性转换,和隐形转换
98 0
【c#入门杂选】-显性转换,和隐形转换
|
C++
【C++操作手册】将字符串转化为数字、数字转化为字符串、字符转化为数字、数字转化为字符
【C++操作手册】将字符串转化为数字、数字转化为字符串、字符转化为数字、数字转化为字符
94 0
|
测试技术
PAT乙级1006.换个格式输出整数(15分)
PAT乙级1006.换个格式输出整数(15分)
58 0

热门文章

最新文章