编译原理之路（二）第三章作业习题解答
题目：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)
want -> other* a (other|a)* e (other|e)* i (other|i)* o (other|o)* u (other|u)*
other -> [bcdfghjklmnpqrstvwxyz]
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-> <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ->0)0,0 | 0,0 |
| 0,1 | 1,2 | 2,2 | (2-> <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ->0)0,0 |
这个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 | <math> <semantics> <mrow> <mi> ϕ </mi> </mrow> <annotation encoding="application/x-tex"> \phi </annotation> </semantics> </math>ϕ |
| {4} | S1.2 | <math> <semantics> <mrow> <mi> ϕ </mi> </mrow> <annotation encoding="application/x-tex"> \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）
(( <math> <semantics> <mrow> <mi> ϵ </mi> </mrow> <annotation encoding="application/x-tex"> \epsilon </annotation> </semantics> </math>ϵ|a)b*)*
NFA状态如下
接下来是子集表
| 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 |
通过肉眼观察其实很容易看错，只看熟不熟练了~
DFA为
小结：
状态图，NFA,DFA的转换其实并不难，因为多做很容易发现套路，难的在于对于比较复杂的表达式极易出错，光靠肉眼检查，哎
而且还很花时间……
