计算理论个人总结

《计算理论个人总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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,0

8、yz£B■若y=V,00,9^xyyz£B2.3DFAM的形式描述为（i2-3Af的5ua41s929iq、q、q?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}•