题目：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-> ϵ \epsilon ϵ->0)0,0 0,0
0,1 1,2 2,2 (2-> ϵ \epsilon ϵ->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 ϕ \phi ϕ
{4} S1.2 ϕ \phi ϕ 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 ϵ|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的转换其实并不难，因为多做很容易发现套路，难的在于对于比较复杂的表达式极易出错，光靠肉眼检查，哎
而且还很花时间……