《计算理论习习题解答》由会员分享，可在线阅读，更多相关《计算理论习习题解答（44页珍藏版）》请在金锄头文库上搜索。
1、计算理论习题解答练习 图给出两台DFA M1和M2的状态图. 回答下述有关问题.a. M1的起始状态是q1b. M1的接受状态集是q2c. M2的起始状态是q1d. M2的接受状态集是q1，q4e. 对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1f. M1接受字符串aabb吗否g. M2接受字符串吗是 给出练习中画出的机器M1和M2的形式描述.M1=(Q1,1,q1,F1) 其中1） Q1=q1,q2,q3,;2） =a,b;3） 1为：a b q1 q2 q3 q2 q1 q3 q3 q2 q14） q1是起始状态5） F1=q2M2=(Q2,2,q2,F2) 其中1） Q
2、2=q1,q2,q3,q4;2） =a,b;3）2为：a b q1 q2 q3 q4 q1 q2 q3 q4 q2 q1q3 q43） q2是起始状态4） F2=q1,q4 DFA M的形式描述为 ( q1，q2，q3，q4，q5，u,d,q3，q3),其中在表2-3中给出。试画出此机器的状态图。q1q5q4q2q3uduuuudddd 画出识别下述语言的DFA的状态图。a)w | w从1开始以0结束001110,100100110,1b)w | w至少有3个10,110011010c) w | w含有子串01010,100,10,1110,10d) w | w的长度不小于3，且第三个符号为0
3、0,10,10,100,11e) w | w从0开始且为奇长度，或从1开始且为偶长度0,100,11或0,1010110f) w | w不含子串1100,10,10,10,10,10,10,1g) w | w的长度不超过51110,1000h)w | w是除11和111以外的任何字符100,10,1i)w | w的奇位置均为1j) w | w至少含有2个0，且至多含有1个10010011111000,1k) ,000,10,111100111110000001l) w | w含有偶数个0，或恰好两个1m) 空集 n) 除空串外的所有字符串0,10,10,1 给出识别下述语言的NFA，且要求符合
4、规定的状态数。000,1a. w | w以00结束，三个状态010,1010,1b. 语言w | w含有子串0101，即对某个x和y，w=x0101y，5个状态.e011101000ec. 语言w | w含有偶数个0或恰好两个1，6个状态。d. 语言0，2个状态。0e. 语言0*1*0*0，3个状态。e0010f. 语言，1个状态。g. 语言0*，1个状态。0证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。证明:设NFA M=Q，,q0,F，F=ri1，rik.添加一个状态p后，ri1，rik分别向p引箭头，将ri1，rik变为非接受状态，p变为接受状态。又因为添加箭头不影响NFA
5、识别语言，所以命题成立。2.14 a 证明：设M是一言B的DFA，交换M的接状态与非接受状态得到一台新的DFA，则这台新的DFA是识别B 的补集，因此，正则语言类受在补运算下封闭。b 举例说明：设M是一台识别语言B的NFA，交换M的接受状态与非接受状态得到一台新的NFA，这台新的NFA不一定识别B的补集。NFA识别的语言类在补集下封闭吗解释你的回答。解：a. M是DFA, M是Q,q0,F,令N=Q,q0,Q-F,设=12n是字母表上任意字符串，因为M与N均为DFA,所以必然存在Q中状态序列r0,r1,rn,使得：r0=q0, (ri, i+1)=ri+1, i=0,n-11)若rnF 则B;
6、2)若rnF,则rnQ-F,即N接受，若B,所以N接受B的补集，即B的补集正则。所以，正则语言类在补运算下封闭。0b. 设B为0。NFA M：0可识别它。依题对它作变换，得到N：则N识别的语言不是B的子集。所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。但是由于NFA识别的语言类与DFA识别的语言类相同，即正则语言类。由a的证明，正则语言类在补运算封闭，可知，NFA识别的语言类-正则语言类在补运算下封闭。若NFA识别语言A，必有 等价的DFA识别A,从而由a知，可交换DFA的接受与非接受状态构造识别A的补集的DFA,则必有等价的NFA识别A的补集。只是，该NFA未必有原NF
7、A交换接受与非接受状态构造而成。 给出一个反例，说明下述构造不能证明定理，即正则语言类在星号运算下封闭。设N=（Q1,1,q1,F1）识别A1。如下构造N=（Q1,1,q1,F1）。N应该识别A1*。a. N的状态集是N1的状态集。b. N的起始状态是N1的起始状态相同。c. F=q1F1。F的接受状态是原来的接受状态加上它的起始状态。d. 定义如下：对每一个q属于Q和每一个a属于。解：设N1识别语言A=至少含有一个1，其中输入字母表为0，1，可知A*=空串或至少含有一个1。10,10,1ea,bab12N1: N:按上述规定构造N的状态图如上。可以看出L(N)=0,1*不等于A*. 所以如此
8、构造的N不一定识别A*.aa,beba123 使用定理中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。10,10,1 a)， b)，解：a), b)aab123b123aba,ba,bab12b12aa,b 给出生成练习中语言的正则表达式。(注: 答案不唯一)a. w | w从1开始以0结束 1*0.b. w | w至少有3个1 *1*1*1*.c. w | w含有子串0101 *0101*.d. w | w的长度不小于3，且第三个符号为0 0*.e. w | w从0开始且为奇长度，或从1开始且为偶长度 0()*1()*.f. w | w不含子串110 (010)
9、*1*.g. w | w的长度不超过5 e.h. w | w是除11和111以外的任何字符 0*10*110*111*.i. w | w的奇位置均为1 (1)*( e1).j. w | w至少含有2个0，且至多含有1个1 0*(00010001100) 0*.k. ,0. 0.l. w | w含有偶数个0，或恰好两个1 (1*01*0)*1*0*10*10*.m. 空集. .n. 除空串外的所有字符串*.对下述每一个语言，给出4个字符串，2个是这个语言的成员，2个不是这个语言的成员。这里假设字母表=a,b.a. a*b* 成员：ab，aab 非成员：aba，bab. a(ba)* 成员：ab，
10、abab 非成员：abb，aac. a*b* 成员：aaa，bbb 非成员：ab，bad. (aaa)* 成员：aaa，aaaaaa 非成员：a，aae.*a*b*a* 成员：aba，aaba 非成员：aa，abbf. ababab 成员：aba，bab 非成员：a，bg. (ea)b 成员：b，ab 非成员：a，bbh. (ababb) * 成员：a，bb 非成员：e，b 使用引理中叙述的过程，把图2-38中的有穷自动机转换成正则表达式。bba,baa123bab12aa), b),解: a) a*b(aba*b)*b) e(ab)a*b(aaabb)a*b*(ae).(注：答案不唯一)利用
11、泵引理证明下述语言不是正则的。a. A1=0n1n2n | n0。证明：假设A1是正则的。设p是泵引理给出的关于A1的泵长度。令S=0p1p2p,S是A1的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含0，xyyz中，0比1、2多，xyyz不是A1的成员。违反泵引理的条件1，矛盾。A1不是正则的。b. A2=www | wa,b*.证明：假设A2是正则的。设p是泵引理给出的关于A2的泵长度。令S=apbapbapb,S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。A2不是正则的。c. A3=a2n | n0.(在这里，a2n表示一串2n个a .)证明：假设A3是正则的。设p是泵引理给出的关于A3的泵长度。令S= a2p，S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。即对任意的i0，xyiz都应在A3中，且xyiz与xyi+1z的
