资源描述：
《计算理论习题问题详解CHAP1new》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、标准文案第一章1.1图给出两台DFAM1和M2的状态图.回答下述有关问题.a.M1的起始状态是q1b.M1的接受状态集是{q2}c.M2的起始状态是q1d.M2的接受状态集是｛q1，q4｝e.对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1f.M1接受字符串aabb吗？否g.M2接受字符串ε吗？是1.2给出练习2.1中画出的机器M1和M2的形式描述.M1=(Q1,Σ,δ1,q1,F1)其中1）Q1={q1,q2,q3,};2）Σ={a,b};3）δ1为：abq1q2q3q2q1q3q3q2q14）q1是起始状态
2、5）F1={q2}M2=(Q2,Σ,δ2,q2,F2)其中1）Q2={q1,q2,q3,q4};2）Σ={a,b};大全标准文案3）δ2为：abq1q2q3q4q1q2q3q4q2q1q3q41）q2是起始状态2）F2={q1,q4}1.3DFAM的形式描述为({q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。试画出此机器的状态图。q1q5q4q2q3uduuuudddd1.6画出识别下述语言的DFA的状态图。a){w
3、w从1开始以0结束}001110,10b){w
4、w至少有3个1}0
5、100110,1大全标准文案0,110011010c){w
6、w含有子串0101}d){w
7、w的长度不小于3，且第三个符号为0}0,100,10,1110,10e){w
8、w从0开始且为奇长度，或从1开始且为偶长度}0,10,10,100,110,100,11或0,1010110f){w
9、w不含子串110}大全标准文案0,10,10,10,10,10,10,1g){w
10、w的长度不超过5}1110,1000h){w
11、w是除11和111以外的任何字符}i){w
12、w的奇位置均为1}100,10,1j){w
13、w至少含有2个0，且至多含有1
14、个1}0010011111000,1k){ε,0}00,10,11大全标准文案l){w
15、w含有偶数个0，或恰好两个1}1100111110000001m)空集n)除空串外的所有字符串0,10,10,11.7给出识别下述语言的NFA，且要求符合规定的状态数。000,1a.{w
16、w以00结束}，三个状态b.语言｛w
17、w含有子串0101，即对某个x和y，w=x0101y｝，5个状态.010,1010,1c.语言｛w
18、w含有偶数个0或恰好两个1｝，6个状态。e011101000e大全标准文案d.语言｛0｝，2个状态。0e.语言0*1*
19、0*0，3个状态。e0010f.语言{ε}，1个状态。0g.语言0*，1个状态。1.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。证明:设NFAM={Q，Σ,δ,q0,F}，F={ri1，……，rik}.添加一个状态p后，ri1，……，rik分别向p引ε箭头，将ri1，……，rik变为非接受状态，p变为接受状态。又因为添加ε箭头不影响NFA识别语言，所以命题成立。1.14a证明：设M是一台语言B的DFA，交换M的接状态与非接受状态得到一台新的DFA，则这台新的DFA是识别B的补集，因此，正则语言类受在补运算下
20、封闭。b举例说明：设M是一台识别语言B的NFA，交换M的接受状态与非接受状态得到一台新的NFA，这台新的NFA不一定识别B的补集。NFA识别的语言类在补集下封闭吗？解释你的回答。解：a.M是DFA,M是{Q,∑,δ,q0,F},令N={Q,∑,δ,q0,Q-F},设ω=ω1ω2…ωn是字母表上任意字符串，因为M与N均为DFA,所以必然存在Q中状态序列r0,r1,…,rn,使得：r0=q0,δ(ri,ωi+1)=ri+1,i=0,…,n-1大全标准文案1)若rnÎF则ωÎB;2)若rnÏF,则rnÎQ-F,即N接受ω，若ωÏB,
21、所以N接受B的补集，即B的补集正则。所以，正则语言类在补运算下封闭。0a.设B为{0}。NFAM：0可识别它。依题对它作变换，得到N：则N识别的语言{ε}不是B的子集。所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。但是由于NFA识别的语言类与DFA识别的语言类相同，即正则语言类。由a的证明，正则语言类在补运算封闭，可知，NFA识别的语言类---正则语言类在补运算下封闭。若NFA识别语言A，必有等价的DFA识别A,从而由a知，可交换DFA的接受与非接受状态构造识别A的补集的DFA,则必有等价的NFA识别A的
22、补集。只是，该NFA未必有原NFA交换接受与非接受状态构造而成。1.15给出一个反例，说明下述构造不能证明定理2.24，即正则语言类在星号运算下封闭。设N=（Q1,Σ,δ1,q1,F1）识别A1。如下构造N=（Q1,Σ,δ1,q1,F1）。N应该识别A1*。a.N的状态集是N
