《计算理论导引习题答案ppt课件.pptx》由会员分享，可在线阅读，更多相关《计算理论导引习题答案ppt课件.pptx（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。计算理论导引习题严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。一、单项选择题1.给定两个集合给定两个集合S和和U,S U那么，那么，S的子的子集可以是（集可以是（A）。）。A、S幂集中的一个元素幂集中的一个元素 B、S中的一个元素中的一个元素C、S UD、U-S2.关关系和谓词的共同点是（系和谓词的共同点是（D）。）。A、都是集合、都是集合B、都是序列、都是序列C、都是笛卡尔积、都是笛卡尔积D、都是函数且值域都是、都是
2、函数且值域都是TRUE,FALSE严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。3.设集合设集合T=0,1，用，用T中元素构造序列，最多中元素构造序列，最多可构造（可构造（D）条序列。）条序列。A、1B、2C、3D、无穷、无穷4.DFA和和NFA的区别在于（的区别在于（A）。）。A A、两者的转移函数的值域不同、两者的转移函数的值域不同 B B、NFANFA能够识别的语言能够识别的语言DFADFA不一定能够识别不一定能够识别C C、DFADFA能够识别的语言能够识别的语言NFANFA不一定能够识别不一定能够识别 D D、NFAN
3、FA比比DFADFA多拥有一个栈多拥有一个栈严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。5.一个语言是正则的，当且仅当（一个语言是正则的，当且仅当（C ）。）。A、可以用一个正则表达式计算它、可以用一个正则表达式计算它 B、可以用一个正则表达式接受它、可以用一个正则表达式接受它C、可以用一个正则表达式描述它、可以用一个正则表达式描述它D、可以用一个正则表达式识别它、可以用一个正则表达式识别它6.若一个语言若一个语言A是非正则的，对于个给定的一是非正则的，对于个给定的一个泵长个泵长p,若存在一个串若存在一个串s=xyz,|s|p
4、，则（，则（C）。）。A、xyyz AB、xz AC、|y|可能大于等于可能大于等于0D、|xy|不可能小于等于不可能小于等于p严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。7.在乔姆斯基范式中，每条规则的右部不允在乔姆斯基范式中，每条规则的右部不允许（许（A）。）。A、出现起始变量、出现起始变量B、出现变量、出现变量C、出现终结符、出现终结符D、出现、出现2个变量个变量严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。二、综合应用题二、综合应用题 1画出识别下述语言
5、的画出识别下述语言的DFA状态图，其中，状态图，其中，字母表为字母表为0,1。1).w|w从从1开始且以开始且以0结束结束；q0q1q21011严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2）w|w含有至少含有至少3个个1；3）w|w含有子串含有子串0101；q0q2q3q11110000,1q0q2q4q101010,11q300严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2.写出下述语言的正则表达式。写出下述语言的正则表达式。1）w|w不含子串不含子串11
6、0；(010)*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不是正则的严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做
7、到及时发现、制止、汇报并处理各类违纪行为或突发事件。2）A2=www|w a,b*假设假设A2是正则的，泵长度为是正则的，泵长度为p令令S=apbapbapb,S是是A2成员，且成员，且S长度大于长度大于p，S可以分成三部分可以分成三部分S=xyz满足泵引理。根据条件满足泵引理。根据条件三三y只包含只包含a，xyyz不是不是A2成员，违反泵引理。成员，违反泵引理。A2不是正则的不是正则的严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。4.给出产生下述语言的上下文无关文法。给出产生下述语言的上下文无关文法。1）w|w至少包含至少包含
8、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|1A严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。5.利用泵引理证明下述语言不是上下文无关利用泵引理证明下述语言不是上下文无关的。的。1）w#t|w,t a,b*,且且w是是t的子串的子串；设该语言上下文
9、无关，p为泵长度。取S=0p1p#0p1p，由泵引理，S可以划分为uvxyz五部分。因为S=uxz也在该语言中，所以vy不包含#。vxy不落在#一边，否则两边长度不同。则#x，则必存在不全为零的i,j使得vy=1i0j严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。当j0，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为泵长度严格执行
10、突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。三、完成下述操作三、完成下述操作1.给出识别语言（给出识别语言（01 001 010）*的的NFA;01110000q0q1q2q3q4q5q6q7q8q9q10q11q12q13q14q15q16q17严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2.下面是一个识别语言下面是一个识别语言M2=0i1j2k|i,j,k0且且i=j或或i=k的的PDAM2的状态图的状态图,请将此请将此PDA转换为转换为CFG。q1q2q5q6q7q3q4,-$0,-0,-,-1,-,-2,0-,$-1,0-,$-2,-严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。CFG G=(V,R,S)V=A11,A12,A13,A14,A88=0,1,2S=A18R:A18-A14A48A14-0A231A23-0A231|A48-A442|严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。A44-A442|A18-0A262|A26-0A262|A551A55-A551|