《计算理论导引习题答案ppt课件》由会员分享，可在线阅读，更多相关《计算理论导引习题答案ppt课件（18页珍藏版）》请在金锄头文库上搜索。
1、计算理论导引习题,一、单项选择题,1. 给定两个集合S和U, SU那么，S的子集可以是（ A ）。 A、 S幂集中的一个元素 B、S中的一个元素 C、 SU D、 U-S 2. 关系和谓词的共同点是（ D ）。 A、都是集合 B、都是序列 C、都是笛卡尔积 D、都是函数且值域都是TRUE, FALSE,3. 设集合T=0,1，用T中元素构造序列，最多可构造（ D ）条序列。 A、1 B、 2 C、3 D、无穷 4. DFA和NFA的区别在于（ A ）。 A、两者的转移函数的值域不同 B、NFA能够识别的语言DFA不一定能够识别 C、DFA能够识别的语言NFA不一定能够识别 D、NFA比DFA多
2、拥有一个栈,5. 一个语言是正则的，当且仅当（ C ）。 A、可以用一个正则表达式计算它 B、可以用一个正则表达式接受它 C、可以用一个正则表达式描述它 D、可以用一个正则表达式识别它 6. 若一个语言A是非正则的，对于个给定的一个泵长p,若存在一个串s=xyz,|s|p，则（ C ）。 A、xyyzAB、xzA C、|y|可能大于等于0 D、|xy|不可能小于等于p,7. 在乔姆斯基范式中，每条规则的右部不允许（ A ）。 A、出现起始变量 B、出现变量 C、出现终结符 D、出现2个变量,二、综合应用题,1画出识别下述语言的DFA状态图，其中，字母表为0,1。 1). w|w从1开始且以0结
3、束；,q0,q1,q2,1,0,1,1,2）w|w含有至少3个1； 3）w|w含有子串0101；,q0,q2,q3,q1,1,1,1,0,0,0,0,1,q0,q2,q4,q1,0,1,0,1,0,1,1,q3,0,0,2. 写出下述语言的正则表达式。 1）w|w不含子串110； (010)*1* 2）w|w的长度不超过5； 3）w|w是除11和111外的任意串； 0*10 *110 * 111 *,3. 利用泵引理证明下述语言不是正则的。 1）A1=0n1n2n|n0; 假设A1是正则的，泵长度为p。 令S=0p1p2p 因为S是A1的成员，且S长度大于p，S可以分成S=xyz三个部分。根据
4、条件三y中只能包含0，而xyyz不是A1成员。所以A1不是正则的,2）A2=www|wa,b* 假设A2是正则的，泵长度为p 令S=apbapbapb,S是A2成员，且S长度大于p，S可以分成三部分S=xyz满足泵引理。根据条件三y只包含a，xyyz不是A2成员，违反泵引理。A2不是正则的,4.给出产生下述语言的上下文无关文法。 1）w|w至少包含3个1； S-A1A1A1A A-A0|A1| 2）w|w以相同的符号开始和结束； S-0A0|1A1|0|1 A-0A|1A|,3）w|w的长度为奇数; S-0A|1A A-0B|1B| B-0A|1A,5. 利用泵引理证明下述语言不是上下文无关的
5、。 1）w#t|w,ta,b*,且w是t的子串； 设该语言上下文无关，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|k2,tia,b*,且存在ij使得ti=tj。 令S=apbp#apbp,p为泵长度,三、完成下述操作,1.给出识别语言（01001010）*的N
6、FA;,0,1,1,1,0,0,0,0,q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15,q16,q17,2.下面是一个识别语言M2=0i1j2k |i,j,k0 且i=j 或 i=k 的PDA M2的状态图,请将此PDA转换为CFG。,q1,q2,q5,q6,q7,q3,q4,-$,0,-0,-,-,1,-,-,2,0-,$-,1,0-,$-,2,-,CFG G=(V, ,R,S) V=A11,A12,A13,A14,A88 =0,1,2 S=A18 R: A18-A14A48 A14-0A231 A23-0A231| A48-A442|,A44-A442| A18-0A262| A26-0A262|A551 A55-A551|,
