计算理论导引

计算理论导引习题一、单项选择题1.给定两个集合S和U,SU那么，S的子集可以是（A）。A、S幂集中的一个元素B、S中的一个元素C、SUD、U-S2.关系和谓词的共同点是（D）。A、都是集合B、都是序列C、都是笛卡尔积D、都是函数且值域都是{TRUE,FALSE}3.设集合T={0,1}，用T中元素构造序列，最多可构造（D）条序列。A、1B、2C、3D、无穷4.DFA和NFA的区别在于（A）。A、两者的转移函数的值域不同B、NFA能够识别的语言DFA不一定能够识别C、DFA能够识别的语言NFA不一定能够识别D、NFA比DFA多拥有一个栈5.一个语言是正则的，当且仅当（C）。A、可以用一个正则表达式计算它B、可以用一个正则表达式接受它C、可以用一个正则表达式描述它D、可以用一个正则表达式识别它6.若一个语言A是非正则的，对于个给定的一个泵长p,若存在一个串s=xyz,|s|p，则（C）。A、xyyzAB、xzAC、|y|可能大于等于0D、|xy|不可能小于等于p7.在乔姆斯基范式中，每条规则的右部不允许（A）。A、出现起始变量B、出现变量C、出现终结符D、出现2个变量二、综合应用题1．画出识别下述语言的DFA状态图，其中，字母表为{0,1}。1).{w|w从1开始且以0结束}；q0q1q210112）{w|w含有至少3个1}；3）{w|w含有子串0101}；q0q2q3q11110000,1q0q2q4q101010,11q3002.写出下述语言的正则表达式。1）{w|w不含子串110}；(0∪10)*1*2）{w|w的长度不超过5}；ε∪∑∪∑∑∪∑∑∑∪∑∑∑∑∪∑∑∑∑∑3）{w|w是除11和111外的任意串}；ε∪0∑*∪10∑*∪110∑*∪111∑∑*3.利用泵引理证明下述语言不是正则的。1）A1={0n1n2n|n0};假设A1是正则的，泵长度为p。令S=0p1p2p因为S是A1的成员，且S长度大于p，S可以分成S=xyz三个部分。根据条件三y中只能包含0，而xyyz不是A1成员。所以A1不是正则的2）A2={|w{a,b}*}假设A2是正则的，泵长度为p令S=apbapbapb,S是A2成员，且S长度大于p，S可以分成三部分S=xyz满足泵引理。根据条件三y只包含a，xyyz不是A2成员，违反泵引理。A2不是正则的4.给出产生下述语言的上下文无关文法。1）{w|w至少包含3个1}；S-A1A1A1AA-A0|A1|ε2）{w|w以相同的符号开始和结束}；S-0A0|1A1|0|1A-0A|1A|ε3）{w|w的长度为奇数};S-0A|1AA-0B|1B|εB-0A|1A5.利用泵引理证明下述语言不是上下文无关的。1）{w#t|w,t{a,b}*,且w是t的子串}；设该语言上下文无关，p为泵长度。取S=0p1p#0p1p，由泵引理，S可以划分为uvxyz五部分。因为S=uxz也在该语言中，所以vy不包含#。vxy不落在#一边，否则两边长度不同。则#∈x，则必存在不全为零的i,j使得vy=1i0j当j≠0，uxz=0p1p-i#0p-j1p不在该语言中当j=0，uvvxyyz中左侧的长度大于右侧，也不再该语言中。因此该语言不是上下文无关的2）{t1#t2##tk|k2,ti{a,b}*,且存在ij使得ti=tj}。令S=apbp#apbp,p为泵长度三、完成下述操作1.给出识别语言（01001010）*的NFA;01εεεεεεεεεεεε110000q0q1q2q3q4q5q6q7q8q9q10q11q12q13q14q15q16q172.下面是一个识别语言M2={0i1j2k|i,j,k≥0且i=j或i=k}的PDAM2的状态图,请将此PDA转换为CFG。q1q2q5q6q7q3q4ε,ε-$0,ε-0ε,ε-ε1,ε-εε,ε-ε2,0-εε,$-ε1,0-εε,$-ε2,ε-εCFGG=(V,∑,R,S)V={A11,A12,A13,A14,…A88}∑={0,1,2}S=A18R:A18-A14A48A14-0A231A23-0A231|εA48-A442|εA44-A442|εA18-0A262|εA26-0A262|A551A55-A551|ε