2019-07-25 17:41 已编辑富途_Android开发

关注

编译原理之路（二）第三章作业习题解答

题目：3.4.1，3.4.2，3.6.2, 3.6.3, 3.6.4，3.7.1, 3.7.3

3.4.1 画状态转换图

首先是NFA图，画了好久，为了保护版权，我还加了自己的签名~

注：如果不能确定NFA中到底需要多少个空串驱动以及状态数量可以仔细阅读算法3.23中介绍的MYT算法中归纳规则部分

1

2

3

4

5

这道题最终还是没能自己画出来，看了网上的，拍案叫绝！精彩！

3.4.2

1)

2)

只需保证前字母小于后字母即可

3

\/\*([^*"]*|".*"|*+[^/])*\*\/
这个画得非常没有把握……

9）

b* | b*a+ | b*a+ba*
以上可以化简为
b*(a+)*(ab)*a*
如图

3.6.2

如3.4.2

3.6.3

以下表格属性为字母，值为字母两端的状态

a	a	b	b
0,0	0,0	0,0	0,0
0,0	0,1	1,1	1,1
0,1	1,2	2,2	2,2
0,1	1,2	2,2	2,2
0,1	1,2	2,2	2,3
0,1	1,2	(2-> $\epsilon </annotation> </semantics> </math>$	0,0
0,1	1,2	2,2	(2-> $\epsilon </annotation> </semantics> </math>$

这个NFA接受"aabb"

3.6.4

可知0可以直接驱动到3,2,1
所以{0,1,2,3}是同一个状态

a	a	b	b
0,1	0,1	1,2	1,2
0,1	0,1	1,2	2,3
0,1	0,1	2,3	2,3
0,1	0,1	2,3	1,2
0,1	3,0	1,2	1,2
0,1	3,0	1,2	2,3
0,1	3,0	2,3	2,3
0,1	3,0	2,3	1,2

当然，0也可先到3的位置，再开始

a	a	b	b
3,0	3,0	1,2	1,2
3,0	3,0	1,2	2,3
3,0	3,0	2,3	2,3
3,0	3,0	2,3	1,2
3,0	0,1	1,2	1,2
3,0	0,1	1,2	2,3
3,0	0,1	2,3	2,3
3,0	0,1	2,3	1,2

3.7.1

将NFA转化为DFA，我们可以用子集构造法实现
子集命名如S1.1的原则是
当出现新状态时

凡是为a移动时小数都是.1,为b移动时小数都是.2依次类推
DFA状态为Sx.y时，move(S,a)为(x+1).1,move(S,b)为(x+1).2,依次类推

图3-26

NFA状态集	DFA状态	a	b
{0,1,3}	S	S1.1	S1.2
{2}	S1.1	S1.1	$\phi </annotation> </semantics> </math>$
{4}	S1.2	$\phi </annotation> </semantics> </math>$	S1.2

其实这个图和原图区别不大，只是少了空串驱动，一开始我还以为画错了

图3.29

NFA状态集	DFA状态	a	b
{0}	S	S1.1	S
{0,1}	S1.1	S2.1	S1.1
{0,1,2}	S2.1	S2.1	S3.2
{0,1,2,3}	S3.2	S2.1	S3.2

图3.30

NFA状态集	DFA状态	a	b
{0,1,2,3}	S	S	S

所以，可以理解为一个状态自己在玩

3.7.3

算法3.20是我们熟悉的子集构造法
算法3.23是MYT算法，关于r=s|t,r=st,r=s*的NFA构造原则

1）

（a|b)*

非常标准的r=s|t加上r=s *构造

值得注意的是，虽然初始状态直接可以到达接受状态，但是接受状态不能到达初始状态，本质上，这是两个不同的状态

子集状态如下

NFA状态集	DFA状态	a	b
{0,1,2,4,7}	S	S1.1	S1.2
{1,2,3,4,6,7}	S1.1	S1.1	S1.2
{1,2,4,5,6,7}	S1.2	S1.1	S1.2

因此，可以画出DFA为

2）

（a*|b*）*
同样是基本操作的叠加

子集状态

NFA状态集	DFA状态	a	b
{0,1,2,3,5,6,7,9,10,11}	S	S1.1	S1.2
{1,2,3,4,5,6,7,9,10,11}	S1.1	S1.1	S1.2
{1,2,3,5,6,7,8,9,10,11}	S1.2	S1.1	S1.2

本质上和上题变化差不多

3）

(( $\epsilon </annotation> </semantics> </math>$

接下来是子集表

NFA状态集	DFA状态	a	b
{0,1,2,4,5,6,7,9,10}	S	S1.1	S1.2
{1,2,3,4,5,6,7,9,10}	S1.1	S1.1	S1.2
{1,2,4,5,6,7,8,9,10}	S1.2	S1.1	S1.2

所以可以画出DFA为

ps:感觉这几题的DFA都一样……

4)

(a|b)*abb(a|b)*
这个正则表达式可以解释为中间有“abb”子串的任意个a和b组成的字符串

下面是子集表

NFA状态集	DFA状态	a	b
{0,1,2,4,7}	S	S1.1	S1.2
{1,2,3,4,6,7,8}	S1.1	S1.1	S2.2
{1,2,4,5,6,7}	S1.2	S1.1	S.1.2
{1,2,3,4,6,7,9}	S2.2	S1.1	S3.2
{1,2,4,5,6,7,10,11,12,14,17}	S3.2	S4.1	S4.2
{1,2,3,4,6,7,8,11,12,14,15,16,17}	S4.1	S4.1	S5.2
{1,2,4,5,6,7,11,12,13,14,16,17}	S4.2	S4.1	S4.2
{1,2,4,5,6,7,9,11,12,13,14,16,17}	S5.2	S4.1	S6.2
{1,2,4,5,6,7,10,11,12,13,14,16,17}	S6.2	S4.1	S4.2