资源描述:
《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■若"=1 0,则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为在泵引理下的分段,贝»■由于xy
0,则"=0t
j}不是正则语言)证:假设D是正则的,而卩是其相应的泵长度。考虑字符串s=而s=xyz为在泵引理下的分段,贝U■由于xy
0,则y=0^015、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为