我们的教材是那本经典的“龙书”： 《Compiler: Principles,Techniques,and Tools》

@H_403_7@

灰常灰常喜欢小监老师的课，就是做作业的记忆太痛苦了。。。

@H_403_7@

3.3.2 试描述下列正则表达式定义的语言

1) a(a|b)*a @H_403_7@ 以a开头且以a结尾，中间由零个或多个a或b的实例构成的串 @H_403_7@ 2) ((ε|a)b*)* @H_403_7@ 零个或多个a或b的实例构成的串 @H_403_7@ 3)(a|b)*a(a|b)(a|b) @H_403_7@ 三个或多个a或b的实例构成的串，且倒数第三个实例一定为a。 @H_403_7@ 4)a*ba*ba*ba* @H_403_7@ 零个或多个a的实例,三个b的实例构成的串。 @H_403_7@ ！！5)(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)* @H_403_7@ 零个或偶数个a的实例，相同个数的b的实例构成的串 @H_403_7@

3.3.5

3) Comments,consisting of a string surround by /* and */,without an intervening*/,unless it is inside double-quotes (") @H_403_7@

3.4.1 给出识别练习3.3.2中各个正则表达式所描述的语言的状态转换图

1) a(a|b)*a @H_403_7@

@H_403_7@

2) ((ε|a)b*)*@H_403_7@

3)(a|b)*a(a|b)(a|b)@H_403_7@

4)a*ba*ba*ba*@H_403_7@

！！5)(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*@H_403_7@

3.6.2 为练习3.3.5中的每一个语言设计一个DFA或NFA

Comments,unless it is inside double-quotes (")@H_403_7@

设计NFA如下: @H_403_7@

@H_403_7@

(感觉这个有些问题，不知道^可不可以用作转移条件。。。。) @H_403_7@

@H_403_7@

1)练习3.6.3 @H_403_7@

2)练习3.6.4@H_403_7@

3)图 2-6@H_403_7@

@H_403_7@

1)图3-26@H_403_7@

2)图3-29@H_403_7@

3)图3-30@H_403_7@

@H_403_7@

1) (a|b)* @H_403_7@ 由算法3.23得到NFA: @H_403_7@

由算法3.20得到DFA: @H_403_7@

2) (a*|b*)* @H_403_7@ 由算法3.23得到NFA: @H_403_7@

3) ((ε|a)b*)* @H_403_7@ 由算法3.23得到NFA: @H_403_7@

此处可以看到 1） 2） 3）表示的语义是等价的，NFA可以有多种表示形式，但DFA是唯一的 @H_403_7@

4)(a|b)*abb(a|b)* @H_403_7@ 由算法3.23得到NFA: @H_403_7@

@H_403_7@