第三章 作业（78CE）【编译原理】 |
您所在的位置：网站首页 › 编译原理第二章作业 › 第三章 作业（78CE）【编译原理】 |
第三章 作业（78CE）【编译原理】
|
第三章 作业【编译原理】前言推荐第三章 作业7812随堂练习随堂练习03-15随堂练习03-15随堂练习03-20随堂练习03-20随堂练习03-27最后前言 2023-3-20 17:05:51 以下内容源自《编译原理》仅供学习交流使用 推荐第二章 作业（6789B）【编译原理】 第三章 作业77.构造下列正规式相应的DFA 1(0|1)*101 ①正规式–>NFA
②NFA–>DFA
③DFA
8.给出下面正规表达式: (1)以01结尾的二进制数串; (2)能被5整除的十进制整数; (3)包含奇数个1或奇数个0的二进制数串; (4)英文字母组成的所有符号串,要求符号串中的字母依照字典序排列; 参考了 https://zhuanlan.zhihu.com/p/363567975 （1）以01结尾的二进制数串 答案： (0|1)*01 （2）能被5整除的十进制整数 答案： (0|5) (1|2|3|4|5||6|7|8|9)(0|1|2|3|4|5||6|7|8|9)*(0|5) 备注：注意分为一位数和多位数两种情况，且十进制整数不能以0开头 （3） 包含奇数个1或奇数个0的二进制数串 答案： 0*1(0|10*1)*|1*0(1|01*0)* 备注：这题考虑包含奇数个1的二进制数串，奇数个1先考虑偶数个1，为 (0|10*1)* ，而包含奇数个1的数串可以拆为 0*+1+0*+ 包含偶数个1的数串，也即 0*+1+ 包含偶数个1的数串，故写为 0*1(0|10*1)* ，包含奇数个0的与之对称。 （4）英文字母组成的所有符号串，要求符号串中的字母按照字典序排列 答案： A*B*...Z*a*b*...z* 备注：这里按照 ACSII 字符表认为 A大写字母的字典序在前 （5）不包含子串 abb的由a和b组成的符号串的全体 答案： b*(a(b|ε))* 备注：根据要求， a 后面要么是a要么是ba要么是空串，也就是一旦出现了a或ba ，后面只能是a或ba ， 这两种情况又都以a为结尾，所以以后也是如此，总结起来就是(a|ab)* ，也即(a(b|ε))* ， 前面没有 a的时候b随便。 顺便拓展几个： （6）每个1都有0直接跟在右边（3.14） 答案： (0|10)* 总结： 这种题不太好摸规律，暂时给个思路，对于没有前缀后缀的要求的字符串， 将每一位可能的结果并在一起求闭包，也就是(d1|d2|... |dn)* ， 如果有，在前面或后面补上，同时根据题意修改di1212.将图3.18的(a)和(b)分别确定化和最少化。
(a)确定化 ①NFA->DFA
②DFA
验证 {a}*(a|b)a 任意多个a打头，aa或ba结尾 (b)最少化 {2,3,4,5} {0,1} Ia 1 3 0 5 1 1 Ib 3 2 5 4 2 4 观察，划分为{{0,1} {2,4} {3,5}}
14.构造一个 DFA,它接受Σ{0,1}上所有满足如下条件的字符串:每个1都有0直接跟在右边。 正规表达式 (0|10)* ①正规表达式 --> NFA
② NFA–>DFA
③DFA
1(简答题) 请画出与以下线性文法G对应的状态转换图。 S →aS|aB B →bB|bC C →cC|c
请画出此状态转换矩阵相应的状态转换图 1(简答题) 请画出此状态转换矩阵相应的状态转换图 · a b c ε S0 {S0} Φ Φ {S1,S2} S1 Φ {S1,S3} Φ Φ S2 Φ Φ {S2} {S3} S3 Φ Φ Φ Φ
请将下图NFA确定化，画出状态矩阵和状态图。 1(简答题) 请将下图NFA确定化，画出状态矩阵和状态图。
答： I Ia Ib Ic {S0,S1,S2,S3} {S0,S1,S2,S3} {S1,S3} {S2,S3} {S1,S3} ∅ {S1,S3} ∅ {S2,S3} ∅ ∅ {S2,S3}
给定正规式1（110*|00*1）0，请画出该正规式对应的NFA 1(简答题) 给定正规式1（110*|00*1）0，请画出该正规式对应的NFA
请将其最小化 1(简答题) 请将其最小化
答： 划分 非终态集 终态集 {1,2,3} {3} 观察I0(1,3)={3} I0(2)={4} 所以划分出{1,3} {2] 观察I1(1,3)=2 划分结束 {1,3}用3代替 结果如图
2023-3-28 18:31:08 祝大家逢考必过 点赞收藏关注哦
|
【本文地址】
今日新闻 |
推荐新闻 |