台乔嗓怀肯翻坍藉凉樊溯绒杉
作业第2章 文法与语言 第2章作业
1、 文法G＝({A,B,S},{a,b,c},P,S), 其中P 为： S→Ac|aB A→ab B→bc写出L(G[S])的全部元素。
评分规则: 参考答案： L(G[S])={abc}评分指南：（1) 与答案一致得2分；（2) 答案式中等号左侧不规范，右侧正确得1分；（3)其它情况得0分。
2、 文法G[N]为：N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？
评分规则: 参考答案： L(G[N])={
| V∈ {0,1,2,3,4,5,6,7,8,9},n>=1}或者 L(G[N])={允许0 开头的非负整数}评分指南：（1)正确得2分；(2)主体（等式的右部）正确得1分；（3)其它情况0分。
3、 考虑下面上下文无关文法：S→SS|SS+|a (1) 说明通过此文法如何生成串aa+a，并为该串构造语法树。(2) G[S]的语言是什么？
评分规则: 参考答案：（1)此文法生成串aa+a的最右推导如下(也可以使用其它推导方式）:S=>SS=>SS=>Sa=>SS+a=>Sa+a=>aa+a, 语法树如下：
（2)该文法生成的语言是：和+的后缀表达式，即逆波兰式。（也可以给出L(G[S])的表达式）评分指南：（1)解题正确得4分，部分正确酌情得1-2分，不正确得0分。（2)解题正确得2分，部分正确酌情得1分，不正确得0分。
4、 文法S→Ac|aB A→ab B→bc 是二义的吗？说明理由。
评分规则: 参考答案：对于串abc (1)S=>Ac=>abc; (2)S=>aB=>abc存在两不同的最右推导。所以，该文法是二义的。（注意：也可采用最左推导）或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。评分指南： 解题正确得5分，部分正确酌情得2分，不正确得0分。
5、 给出生成下述语言的上下文无关文法：
评分规则: 参考答案：
评分指南：每个解答正确得3分，7个解答正确得21分；每个解答部分正确得1分，不正确得0分。注意：上面答案不唯一，只要文法能正确定义相应得语言就算正确。
6、 给出生成下述语言的三型文法：
评分规则: 参考答案：
评分指南：每个解答正确得3分，3个解答正确得9分；每个解答部分正确得1分，不正确得0分。注意：上面答案不唯一，只要文法能正确定义相应得语言就算正确。
作业第3章 词法分析 第3章词法分析作业（适用于软件工程专业）
1、 构造下列正规式相应的DFA.1(0|1)*101
评分规则: 以下4步全对得10分，其中第1步占2分，第2步占3分，3步各占1分，第4步占2分。注意：下面状态图或矩阵中结点的命名方式可以因人而异，但结点个数不能与参考答案不同。
2、 已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。
评分规则: 以下4步全对得10分，其中第1步占2分，第2步占3分，3步各占1分，第4步占2分。注意：（1)下面状态图或矩阵中结点的命名方式可以因人而异，但结点个数不能与参考答案不同。（2）第1步也可以是画出状态转换图。
3、 给文法G[S]：S→aA|bQ A→aA|bB|b B→bD|aQ Q→aQ|bD|b D→bB|aA E→aB|bF F→bD|aE|b构造相应的最小的DFA。
评分规则: 以下5步全对得12分，其中第1步占2分，第2步占3分，3步各占1分，第4步占2分，第5步4分。注意：（1)下面状态图或矩阵中结点的命名方式可以因人而异，但结点个数不能与参考答案不同。（2）第1步也可以是画出状态转换图。
第4步全对得2分，第5步全对得4分，部分对酌情给分。
4、 为下边所描述的串写正规式，字母表是 {a,b}.(1)以ab 结尾的所有串(2)包含偶数个b 且含任意数目a 的所有串
评分规则: 全对得6分，每题占3分，每题部分对得1分。参考答案如下：(1) (a|b)ab(2) bb(bb)a*
作业第3章 词法分析 第3章词法分析作业（适用于数据科学与大数据技术专业）
1、 为下边所描述的串写正规式，字母表是 {a,b}. (1)以ab 结尾的所有串(2)包含偶数个b 但不含a 的所有串(3)只包含一个a 的所有串(4)包含ab 子串的所有串
评分规则: （1）(a|b)ab（2）bb(bb)（3）bab（4）(a|b)ab(a|b)
2、 给定一个有穷自动机（FA）表示如下：
请回答如下问题：（1）串000111是否能被上面自动机所接受，请说明理由。（2）请写出上面FA的五元组表示形式（3）该FA是确定的有穷自动机吗？为什么？
评分规则: 教师批改
作业第3章 词法分析 词法分析实验（软件工程专业）
1、 词法分析实验要求：1. 每位学生任选附件中4道实验题目之一，可以独立完成，也可以4位学生为一组完成。2. 4位学生为一组完成为加分项。要求每位学生完成1道实验题，并考虑前后的接口衔接问题，最后得到一个完整的词法分析程序自动构造工具。4位学生为一组完成情况需要在通过程序的在线测试后到任课老师处登记。3. 所有程序需要在CG编译原理实验在线评测平台（http://192.168.251.201）通过，该平台需要大家通过校园VPN登录后使用，开放时间另行通知。
评分规则: 教师批改
上方为免费预览版答案，如需购买完整答案，请点击下方红字
点关注，不迷路，微信扫一扫下方二维码
关注我们的公众号：阿布查查 随时查看答案，网课轻松过
为了方便下次阅读，建议在浏览器添加书签收藏本网页
电脑浏览器添加/查看书签方法
1.按键盘的ctrl键+D键，收藏本页面
2.下次如何查看收藏的网页？
点击浏览器右上角-【工具】或者【收藏夹】查看收藏的网页
手机浏览器添加/查看书签方法
一、百度APP添加/查看书签方法
1.点击底部五角星收藏本网页
2.下次如何查看收藏的网页？
点击右上角【┇】-再点击【收藏中心】查看
二、其他手机浏览器添加/查看书签方法
1.点击【设置】-【添加书签】收藏本网页
2.下次如何查看收藏的网页？
点击【设置】-【书签/历史】查看收藏的网页
拾昂贸假惺枯库嚼熔派蓬别统