3-计算理论总结

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

1、正则语言M]aM22.1图给出两台DFAMi和M2的状态图.回答下述有关问题.a.Mi的起始状态是qib.Mi的接受状态集是{q?}C.M2的起始状态是5d.M2的接受状态集是(qi，q4)e.对输入aabb,Mi经过的状态序列是qi，q2.q3，qi，qif.Mi接受字符串aabb吗？否，因为无法到达终态q2g.M2接受字符串£吗？是2.6画出识别下述语言的DFA的状态图。DFA和NFA的区别：DFA对于每个输入的字符，都能确定的指定到一个确定的状态；而NFA的每个字符，指定的不一定是同一个状态，可能同时指向不同状态。a){w

2、w从1开始以0结束}b){w

3、w至少有3个1}重点c){w

4、

5、w含有子串0101}d){w

6、w的长度不小于3,Ji第三个符号为0}1e){w

7、w从0开始且为奇长度，或从1开始且为偶长度}最后一个接受状态若是输入0,则无法返回到接受状态，因此不会有H0g){w

8、w的长度不超过5}h){w

9、w是除11和111以外的任何字符}注：11和111是指接受状态后的结果。i){w

10、w的奇位置均为1}注：起始接受状态中，输入0后，则无法回到接受状态，因此不会有影响j){wIw至少含有2个0,且至多含有1个1}k){£,0}I){w

11、w含有偶数个0,或恰好两个1}m)空集一Cp(un)除空串外的所有字符串泵引理:若4是一个正则语言，则存在数卩使得：如果s是4中任—长度

12、不小于P的字符串，贝Us可以被分为3段，即s=xyz,满足n对每个。>0,有①/zGA；y>o；I讪

13、n>0}不是正则语言）证：假设3是正则的，而卩是其相应的泵长度。考虑字符串s=^lPeB,而.s=xyz为在泵引理下的分段，贝U■若y=0',0VtVp,则列gzgB■若"=10,则xyyzB例17（证明B={ww中0,1的个数相同}不是正则语言）证：假设3是正则的，而p是其相应的泵长度。考虑字符串^>=0pPeB,而.s=xyz为在泵引理下的分段，贝U■由于xy

14、0vtSp。■ifrjxyyzBo例］8（证明C={www€{0,1}*}不是正则语言）证：假设C是正则的，而p是其相应的泵长度。考虑字符串S=0^10^1eC,而s=xyz为在泵引理下的分段，贝»■由于xy0,则"=0tj}不是正则语言)证：假设D是正则的，而卩是其相应的泵长度。考虑字符串s=而s=xyz为在泵引理下的分段，贝U■由于xy0,则y=0^0

15、E+TnT+FnF+ana+ac.EnE+TE+T+F^T+F+a=>F+a+a^a+a+ad.E=>T=>F=>(E)=>(T)=>(F)=>((E))=>((T))=>((F))=>@))3.2a.利用语言A={ambncn

16、m,20}和B={anbncm

17、m,n20}以及例3.20,证明上下文无关语言在交的运算下不封闭。证明：a.先说明A,B均为上下文无关文法，对A构造CFGQStbS

18、T

19、£TTbTc

20、£对B,构造CFGC2S—Sc

21、R

22、sRTaRb由此知A,B均为上下文无关语言。但是由例3.20,AnB={anbncn

23、n>0M<是上下文无关语言，所以上下文无关语言在交的运算下不

24、封闭。3.3设上下文无关文法G：R->XRX

25、SS~aTb

26、bTaT->XTX

27、X

28、eX-*a

29、b回答下述问题：a.G的变元和终结符是什么？起始变元是哪个？答：变元是：R，X,S,T；起始变元是Rc终结符是：a,b,eb.给出L(G)中的三个字符串。答：ab,ba,aaboC.给出不在L(G)中的三个字符串。答：a,b,£d.是真是假：T=>ahao答：假*是真是假：T=>abao答：真f.是真是假：TnT°答：假g・*是真是假：TnT°答：假h.*是真是假：XXXaaba。答：真i.*是真是假：X=>abao答：假■J-*是真是假：T=>XX。答:真k・*是真是假：T.XXX。答：真I.

30、是真是假：X=>£。答：假四、何使用它的栈。用‘匕，br”表示当机器从输入中读到Q时可以用C替换栈顶的符号方。Q、b和C中的任何一个都可以是.如果a是"则机器做这个转移，而不读输人中的任何符号。如果b是s则机器做这个转移，而不读栈中的任何符号，也不从栈中弹出任何符号。如果c是•则机器做这个转移，而不在栈中写任何符号。Le^eO.etO0.0->£尸£表示“空”1)0,£・>0当读取到输入的字符为0吋，将0压入栈(此吋0为