【编译原理】正则表达式
08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://blog.csdn.net/xiaowei_cqu/article/details/7747205
《编译原理》第三章习题
我们的教材是那本经典的“龙书”：《Compiler: Principles, Techniques, and Tools》
灰常灰常喜欢小监老师的课，就是做作业的记忆太痛苦了。。。
3.3.2 试描述下列正则表达式定义的语言
1)a(a|b)*a以a开头且以a结尾，中间由零个或多个a或b的实例构成的串
2)((ε|a)b*)*
零个或多个a或b的实例构成的串
3)(a|b)*a(a|b)(a|b)
三个或多个a或b的实例构成的串，且倒数第三个实例一定为a。
4)a*ba*ba*ba*
零个或多个a的实例,三个b的实例构成的串。
！！5)(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*
零个或偶数个a的实例，相同个数的b的实例构成的串
3.3.5
3)Comments,consistingofastringsurroundby/*and*/,withoutanintervening*/,unlessitisinsidedouble-quotes(")(\/\*) (.*^(\/\*)) (“(.*)”|ε) (.*^(\/\*)) (\*\/)
3.4.1 给出识别练习3.3.2中各个正则表达式所描述的语言的状态转换图
1)a(a|b)*a
2) ((ε|a)b*)*
3)(a|b)*a(a|b)(a|b)
4)a*ba*ba*ba*
！！5)(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*
3.6.2 为练习3.3.5中的每一个语言设计一个DFA或NFA
设计NFA如下:
(感觉这个有些问题，不知道^可不可以用作转移条件。。。。)
3.6.5 给出如下练习中的NFA的转换表
1)练习3.6.3
2)练习3.6.4
3)图 2-6
3.7.1 将下列图中的NFA转换为DFA
1)图3-26
2)图3-29
3)图3-30
3.7.3 用算法3.23和3.20将正则表达式转换为DFA
1) (a|b)*
由算法3.23得到NFA:
由算法3.20得到DFA:
2) (a*|b*)*
由算法3.23得到NFA:
由算法3.20得到DFA:
3) ((ε|a)b*)*
由算法3.23得到NFA:
由算法3.20得到DFA:
此处可以看到 1） 2） 3）表示的语义是等价的，NFA可以有多种表示形式，但DFA是唯一的
4)(a|b)*abb(a|b)*
由算法3.23得到NFA:
由算法3.20得到DFA:
转载请注明出处：http://blog.csdn.net/xiaowei_cqu/article/details/7764967
相关推荐
wangzhaotongalex 2020-10-20
wyq 2020-11-11
TLROJE 2020-10-26
风雨断肠人 2020-10-13
duanqingfeng 2020-09-29
rechanel 2020-11-16
luofuIT成长记录 2020-09-22
phphub 2020-09-10
taomengxing 2020-09-07
MaggieRose 2020-08-19
flyingssky 2020-08-18
山水沐光 2020-08-18
jyj00 2020-08-15
AHuqihua 2020-08-09
山水沐光 2020-08-03