欢迎来到天天文库
浏览记录
ID:47279032
大小:394.56 KB
页数:26页
时间:2019-08-26
《计算理论个人总结》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、第一章:法。如果二元关系R满足下述3个条件:1)R是自反的,即对每一个文・xRjc.2)R是对称的,即对每一个工和y,刃约当且仅当3)R是传递的'即对每一个Z.,和乂,工心和yR=鑼涵hR—则R是一个等价关系°1.7对下列毎一小題,给出一个満足捋定条件的关系。a.自反的和对称的,但不是传递的。b.自反的和传递的,但不是对称的。c・对称的和传递的,但不迪自反的。答案:A:
2、x-y
3、<=5B:x<=yC:第二章:正则语言有穷自动机是描述能力、资源极其有限的计算机的模型有穷自动机是一个五元组(Q刀Qqo,F),其中■状态集:Q是一个有穷集合;■字母表:刀
4、是一个有穷集合;■转移函数:d:QX刀一>Q,6(i,a)=y;■起始状态q()€Q;■接受状态集FQQ;■L(M)={胡3至少有一个1且最后的1后面有偶数个0}■考虑该有限自动机是否接受字符串110L1010;■若A是机器A/接受的全体字符串集合,则称月是"的语言,记为厶(A/)=Ao也称为M识别/接爻A;■如果"不接受任何字符串,则其仍然识别一个语言,即空语言0;例2(考虑M=({如“2},{0,1}0如,“2}))L(Af)={创3以7结束}例3(考虑A/=({qi,©},{OJ}0q“{qi}))注意:由于起始状态也是接受状态,因此空串s€
5、L(M)L(Af)={cu
6、cu=£或以0结束}确定型有穷自动机(DFA)与非确定性有穷自动机(NFA)的区别:■DFA中每个状态对于字母表中的每个符号恰有一个转移箭头射出;■NFA中每个状态对于字母表中的每个符号可能有0、1或多个转移箭头射出;■DFA中转移箭头的标号是字母表中的符号;■NFA中转移箭头的标号可以是字母表中的符号或£,且从一个状态可能有多个标有£的转移箭头;例]6(证明E={Onln
7、n>0}不是正则语言)证:假设£是正则的,而p是其相应的泵长度。考虑字符串s=€B,而s=xyz为在泵引理下的分段,则■若y=0f,08、yz£B■若y=V,00,9^xyyz£B2.3DFAM的形式描述为(i2-3Af的5ua41s929iq、q、q?4gjq、机jb.Iwfw的长度不小于3,且第3个符号为09、c.U-lw从0开始且为奇长度.或者从1开始且为偶长度}d.IwIw不含子串1101e.iwIu«的长度不趙过5}f.10、fwlw是除11和111之外的任何字符审}g.ww的奇位臂均为11h.wiv至少含两个0,且至多含一个1}k・匕01Liwlw有偶数个0或恰好两个1}m-空集n.除空串之外的所有字符串2.4画岀识别下述语言的DFA的状态图。a){w11、w从1开始以0结束}b){w12、w至少有3个1}c){w13、w含有子串0101}d){w14、w的长度不小于3,且第三个符号为0}100,CP"e){w15、w从0开始且为奇长度,或从1开始且为偶长度}nf){w16、w不含子串110}g){w17、w的长度不超过5}h){w18、w是除11和111以外的任何字符}i){w19、w的奇位置20、均为1}00/Cwj){wIw至少含有2个0,且至多含有1个1}0000k){£,0}1I){w21、w含有偶数个0,或恰好两个1}m)空集n)除空串外的所有字符串确定出有穷白动机Gba»bb)图2-37练习2」2中的两台NFA把下图中的两台非确定型有穷自动机转换成2.12使用定理2.19中给出的构造,等价的确定型有穷自动机。2.17利用泵引理讦明下述诸言不是正则的。b・A2={www22、wEIafA23、*}©c.=U2Ic(在这里,/衣示一串2”个a。)2.17利用泵引理证明下述语言不是正则的。nnna.Ai={01224、n>0}o证明:假设A】是正则的。25、设p是泵引理给出的关于A】的泵长度。令S=0PlP2VS是Al的一个成员且S的长度大于P,所以泵引理保证S可被分成3段S二xyz且满足泵引理的3个条件。根据条件3,y中只含0,xyyz中,0比1、2多,xyyz不是Ai的成员。违反泵引理的条件1,矛盾。・・・Ai不是正则的。b.A2={wwwIwg{a,b}*}.证明:假设A2是正则的。设P是泵引理给出的关于A2的泵长度。令S=aPbaPbaPb,VS是A2的一个成员且S的长度大于p,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3,y中只含a,所以xyyz中第一个a的个数将26、比后两个a的个数多,故xyyz不是A?的成员。违反泵引理的条件1,矛盾。・・・A2不是正则的。c.A3={a2nI20}•
8、yz£B■若y=V,00,9^xyyz£B2.3DFAM的形式描述为(i2-3Af的5ua41s929iq、q、q?4gjq、机jb.Iwfw的长度不小于3,且第3个符号为0
9、c.U-lw从0开始且为奇长度.或者从1开始且为偶长度}d.IwIw不含子串1101e.iwIu«的长度不趙过5}f.
10、fwlw是除11和111之外的任何字符审}g.ww的奇位臂均为11h.wiv至少含两个0,且至多含一个1}k・匕01Liwlw有偶数个0或恰好两个1}m-空集n.除空串之外的所有字符串2.4画岀识别下述语言的DFA的状态图。a){w
11、w从1开始以0结束}b){w
12、w至少有3个1}c){w
13、w含有子串0101}d){w
14、w的长度不小于3,且第三个符号为0}100,CP"e){w
15、w从0开始且为奇长度,或从1开始且为偶长度}nf){w
16、w不含子串110}g){w
17、w的长度不超过5}h){w
18、w是除11和111以外的任何字符}i){w
19、w的奇位置
20、均为1}00/Cwj){wIw至少含有2个0,且至多含有1个1}0000k){£,0}1I){w
21、w含有偶数个0,或恰好两个1}m)空集n)除空串外的所有字符串确定出有穷白动机Gba»bb)图2-37练习2」2中的两台NFA把下图中的两台非确定型有穷自动机转换成2.12使用定理2.19中给出的构造,等价的确定型有穷自动机。2.17利用泵引理讦明下述诸言不是正则的。b・A2={www
22、wEIafA
23、*}©c.=U2Ic(在这里,/衣示一串2”个a。)2.17利用泵引理证明下述语言不是正则的。nnna.Ai={012
24、n>0}o证明:假设A】是正则的。
25、设p是泵引理给出的关于A】的泵长度。令S=0PlP2VS是Al的一个成员且S的长度大于P,所以泵引理保证S可被分成3段S二xyz且满足泵引理的3个条件。根据条件3,y中只含0,xyyz中,0比1、2多,xyyz不是Ai的成员。违反泵引理的条件1,矛盾。・・・Ai不是正则的。b.A2={wwwIwg{a,b}*}.证明:假设A2是正则的。设P是泵引理给出的关于A2的泵长度。令S=aPbaPbaPb,VS是A2的一个成员且S的长度大于p,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3,y中只含a,所以xyyz中第一个a的个数将
26、比后两个a的个数多,故xyyz不是A?的成员。违反泵引理的条件1,矛盾。・・・A2不是正则的。c.A3={a2nI20}•
此文档下载收益归作者所有