DOC《第三章习题解答》

8 } = E ?(D, b) = followpos(2)∪followpos(7) = D ?(E, a) = followpos(1)∪followpos(3)∪followpos(6) = E ?(E, b) = followpos(2)∪followpos(4)∪followpos(7) = { 1, 2, 3, 5, 6, 7,

8 } = F ?(F, a) = followpos(1)∪followpos(3)∪followpos(6) = E ?(A, b) = followpos(2)∪followpos(7) = D (Aho)3.21 最小化3.18得到的DFA d) 解: 初始划分:{A, B, C}, {D, E, F} {A, B, C}――{A, B}, {C} {A, B}――{A}, {B} 3.22 正规式的等价可以通过对应的最小化的DFA的结构等价性来证明,利用这种方法,证明下列正规式的等价性 (a | b)* (a* | b*)* ((? | a)b*)* 由

16、

17、

18、21结果可知 (陈)7 构造下列正规式对应的DFA 解法:可正规式(NFA(DFA,或者正规式(DFA 1(0 | 1)*101 1(1010* | 1(010)*1)*0 0*10*10*10* (00 | 11)*((01 | 10)(00 | 11)*(01 | 10)(00 | 11)*)* (陈)8 为下列语言写出正规定义(或正规式、正规文法、有限自动机) 以01结尾的

0、1串解:(0 | 1)*01 能被5整除的十进制整数 解:[1-9][0-9]*(0 | 5) |

0 |

5 包含奇数个1和奇数个0的二进制串 解:(00 | 11)*(01 | 10)((01 | 10)+(00 | 11)*(01 | 10)+)* 解法见Aho3.7f (陈)10 一个人带一只狼、一只羊和一颗白菜过河,每次人只能将一样东西摆渡到对岸.而在无人的情况下,狼会吃掉羊,羊会吃掉白菜.目标,人将三样东西都摆渡到对岸,羊和白菜都不被吃掉.利用有限自动机得到渡河的方法 解:M――人,W――狼,S――羊,C――白菜, 状态――哪些东西在原岸,如:MWS,表示人、狼、羊在原岸(白菜在目的岸) 动作――人将一样东西摆渡到对岸(原(目的――表示为(,也可能是目的(原――表示为() 不满足要求的状态为死状态,如:WS、SC、… 初态:MWSC,终态:?,初态到终态的一条路径――渡河方案. ?(MWSC, (MW) = SC (红色表示死状态) ?(MWSC, (MS) = WC ?(MWSC, (MC) = WS ?(MWSC, (M) = WSC ?(WC, (MW) = MWSC (蓝色表示出现过的状态) ?(WC, (M) = MWC ?(WSC, (M) = MWSC ?(MWC, (MW) = C ?(MWC, (MC) = W ?(MWC, (M) = WC ?(C, (MW) = MWC ?(C, (MS) = MSC ?(C, (M) = MC ?(W, (MS) = MWS ?(W, (MC) = MWC ?(W, (M) = MW ?(MSC, (MS) = C ?(MSC, (MC) = S ?(MSC, (M) = SC ?(MWS, (MW) = S ?(MWS, (MS) = W ?(MWS, (M) = WS ?(S, (MW) = MWS ?(S, (MC) = MSC ?(S, (M) = MS ?(MS, (MS) = ? 终态! ?(MS, (M) = S 状态转换序列:MWSC→WC→MWC→C→MSC→S→MS→? 动作序列:(MS,(M,(MW,(MS,(MC,(M,(MS (陈)12 将下面DFA最小化 解: 初始划分:{0, 1}, {2, 3, 4, 5} {2, 3, 4, 5}――{2, 4}, {3, 5} (陈)14 构造DFA,它接受?={0, 1}上所有满足如下条件的符号串:每个1都有0直接跟在右边. (陈)17 下面符号串集合是否为正规集?若是,写出正规式,否则,给出证明 L1 = {anbn | n >

= 0} 解:不是正规集,证明见讲义4-1第51页L2 = {x | x中含有相同个数的a和b} 解:不是正规集,证明类似a) L3 = {ap | p为素数} 解:不是正规集 证明:假设L3是正规集,对应DFA D的状态数为k. 令p

0、p

1、…、pk为前k+1个素数, s

0、s

1、…、sk为D读入ap

0、ap

1、…apk后到达的状态. 显然,必有0........