【20200401】编译原理课程课业打卡十二之求解正规文法对应正规式

2023-09-21 18:36| 来源: 网络整理| 查看: 265

【20200401】编译原理课程课业打卡十二之求解正规文法对应正规式一、课业打卡十二之求解正规文法对应正规式二、知识巩固1、关于正文法&正规式2、求解方法步骤3、例题拓展叮嘟！这里是小啊呜的学习课程资料整理。好记性不如烂笔头，今天也是努力进步的一天。一起加油进阶吧！在这里插入图片描述

一、课业打卡十二之求解正规文法对应正规式给出下述正规文法所对应的正规式： S->0A|1B A->1S|1 B->0S|0

题解如下：在这里插入图片描述

故 S=(01|10)*|(01|10) 二、知识巩固 1、关于正文法&正规式

正规文法与正规式都是描述正规集的工具。对任意一个正规文法，存在定义统一语言的正规式；反之，对每个正规式存在一个生成同一语言的正规文法。对任何正规文法G，存在定义同一语言的正规式 r。

2、求解方法步骤

① 将文法中的规则写成关于每个非终结符的正规式方程，得到一个方程组；

（方程组中用“+”代替正规式中的“|”）

② 依照求解规则：在这里插入图片描述求解示例：

（1）例题一：

Z → 0A A → 0A|0B B → 1A|ε

题解如下：

正规式： A = 0A|0B = 0A + 0B = 0A +0(1A + ε) = 0A+01A+0ε = 0A + 01A +0 = (0 + 01) A + 0 = (0101)*0 Z = 0A = 0(0|01)*0

（2）例题二：

Z → U0|V1 U → Z1|1 V → Z0|0

题解如下：

正规式：　　Z=U0+V1 　　U=Z1+1 　　V=Z0+0 　　　　Z=(Z1+1)0+(Z0+0)1 　　 =Z10+10+Z01+01 　　 =Z(10+01)+10+01 　　 =(10|01)*(10|01)

（3）例题三：

S → aA A → bA|aB|b B → aA

题解如下：

正规式：　　S=aA,A=bA+aB+b,B=aA 　　A=bA+aaA+b 　　 =(b+aa)A+b 　　　　S=a(b|aa)*b

（4）例题四：

I → l|Il|Id

题解如下：

正规式：　　I=l+Il+Id 　　 =I(l+d)+l 　　 =(l|d)*l

Ending！更多课程知识学习记录随后再来吧！

就酱，嘎啦！

在这里插入图片描述

注：人生在勤，不索何获。

【本文地址】

今日新闻