将正规文法转化为正规式

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

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

通过一道例题来讲解:

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


目录
相关文章
|
17天前
|
文字识别
印刷文字识别产品使用合集之 识别营业执照时,如果企业名称中有中英文括号,请问是统一转换为英文括号返回还是按实际的括号类型返回
印刷文字识别产品,通常称为OCR(Optical Character Recognition)技术,是一种将图像中的印刷或手写文字转换为机器编码文本的过程。这项技术广泛应用于多个行业和场景中,显著提升文档处理、信息提取和数据录入的效率。以下是印刷文字识别产品的一些典型使用合集。
|
4天前
用人话教会你各个进制的意思和进制间的转化!!!
用人话教会你各个进制的意思和进制间的转化!!!
|
1月前
|
算法
年和日转化为天干地支
年和日转化为天干地支
7 0
|
8月前
|
C#
C#小知识之中英文转换、去空格
# 一、中英文转换 ## 1、安装NPinYin ![请在此添加图片描述](https://developer-private-1258344699.cos.ap-guangzhou.myqcloud.com/column/article/5877188/20231031-1f77b9b6.png?x-cos-security-token=kcWkaWALSQ5t0gKzZRkVwYOOBJMLQ8Ra8df6748cc017b8b22443671efb8aed172ct0qMmH-Si3jPfLmVc91udBHTdfdp2n1Qk-hBfLRQF5l22U2cHOMKfU7b0bWfl1t
87 0
C#小知识之中英文转换、去空格
|
1月前
【全网最精简】一行代码解决千万位以上的数字格式化为银行金额数字格式/货币格式(如:¥1,000,000,000.00)
【全网最精简】一行代码解决千万位以上的数字格式化为银行金额数字格式/货币格式(如:¥1,000,000,000.00)
|
1月前
7-7 念数字 (15 分)(用数组简化判断过程)
7-7 念数字 (15 分)(用数组简化判断过程)
27 0
|
10月前
数字的转化规则?
转换规则:不管你要转的数据是什么,都是一位一位的去检测,如果第一位可以转成数字,就转,依次往后看每一位,直到碰到不能转或者转完为止,如果转不成就直接NaN
|
10月前
字符串的转化规则?
null和 undefined类型 ,null 转换为 “null”,undefined 转换为 “undefined”,
|
11月前
如何用正则表达式判断手机号格式正不正确
如何用正则表达式判断手机号格式正不正确
115 0