资源描述：
《可计算性与计算复杂性(计算原理答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1.6画出识别下述语言的DFA的状态图。a){w
2、w从1开始以0结束}001110,10b){w
3、w至少有3个1}0100110,10,110011010c){w
4、w含有子串0101}d){w
5、w的长度不小于3，且第三个符号为0}0,100,10,1110,10e){w
6、w从0开始且为奇长度，或从1开始且为偶长度}0,10,10,100,110,100,11或0,1010110f){w
7、w不含子串110}0,10,10,10,10,10,10,1g){w
8、w的长度不超过5}1110,1000h){w
9、w是除11
10、和111以外的任何字符}100,10,1i){w
11、w的奇位置均为1}j){w
12、w至少含有2个0，且至多含有1个1}0010011111000,1k){ε,0}00,10,11l){w
13、w含有偶数个0，或恰好两个1}1100111110000001m)空集n)除空串外的所有字符串0,10,10,11.29利用泵引理证明下述语言不是正则的。a.A1={0n1n2n
14、n³0}。证明：假设A1是正则的。设p是泵引理给出的关于A1的泵长度。令S=0p1p2p,∵S是A1的一个成员且S的长度大于p，所以泵引理保证S可被分成
15、3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含0，xyyz中，0比1、2多，xyyz不是A1的成员。违反泵引理的条件1，矛盾。∴A1不是正则的。b.A2={www
16、wÎ{a,b}*}.证明：假设A2是正则的。设p是泵引理给出的关于A2的泵长度。令S=apbapbapb,∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。∴A2不
17、是正则的。c.A3={a2n
18、n³0}.(在这里，a2n表示一串2n个a.)证明：假设A3是正则的。设p是泵引理给出的关于A3的泵长度。令S=a2p，∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。即对任意的i³0，xyiz都应在A3中，且xyiz与xyi+1z的长度都应是2的幂.而且xyi+1z的长度应是xyiz的长度的2n倍(n³1)。于是可以选择足够大的i，使得
19、xyiz
20、=2n>p.但是
21、xyi+1z
22、-
23、xyiz
24、=
25、y
26、£p.即
27、xyi+1z
28、<2
29、n+1,矛盾。∴A3不是正则的。1.46证明：a)假设{0n1m0n
30、m,n≥0}是正则的，p是由泵引理给出的泵长度。取s＝0p1q0p，q>0。由泵引理条件3知，
31、xy
32、≤p，故y一定由0组成，从而字符串xyyz中1前后0的数目不同，即xyyz不属于该语言，这与泵引理矛盾。所以该语言不是正则的。b)假设{0n1n
33、n≥0}的补集是正则的，则根据正则语言在补运算下封闭可得{0n1n
34、n≥0}是正则的，这与已知矛盾，故假设不成立。所以该语言不是正则的。c)记c={0m1n
35、m≠n}，┐c为c的补集，┐c∩0*1*
36、={0n1n
37、n≥0}，已知{0n1n
38、n≥0}不是正则的。若┐c是正则的，由于0*1*是正则的，那么┐c∩0*1*也应为正则的。这与已知矛盾，所以┐c不是正则的。由正则语言在补运算下的封闭性可知c也不是正则的。d){w
39、wÎ{0,1}*不是一个回文}的补集是{w
40、wÎ{0,1}*是一个回文}，设其是正则的，令p是由泵引理给出的泵长度。取字符串s=0p1q0p，显然s是一个回文且长度大于p。由泵引理条件3知
41、xy
42、≤p，故y只能由0组成。而xyyz不再是一个回文，这与泵引理矛盾。所以{w
43、wÎ{0,1}*是一个
44、回文}不是正则的。由正则语言在补运算下的封闭性可知{w
45、wÎ{0,1}*不是一个回文}也不是正则的。2.4和2.5给出产生下述语言的上下文无关文法和PDA，其中字母表S={0,1}。e,1®e1,e®10,e®ee,1®ee,1®ea.{w
46、w至少含有3个1}S→A1A1A1AA→0A
47、1A
48、eb.{w
49、w以相同的符号开始和结束}1,e®11,e®e0,e®e0,e®01,1®e0,0®eS→0A0
50、1A1A→0A
51、1A
52、e1,e®e0,e®e1,e®e0,e®ec.{w
53、w的长度为奇数}S→0A
54、1AA→0B
55、
56、1B
57、eB→0A
58、1Ad.{w
59、w的长度为奇数且正中间的符号为0}S→0S0
60、1S1
61、0S1
62、1S0
63、01,e®00,e®e0,e®01,0®e0,0®ee,e®$e,$®e1,e®1e,1®e0,e®0e,1®ee,e®$e,$®e1,0®e0,1®ee.{w
64、w中1比0多}S→A1AA→0A1
65、1A0
66、1A
67、AA
68、ea.{w
69、w=wR}S→0S0
70、1S1
71、1
72、01,e®10,e®
