计算理论习题解答

精品-可编辑-计算理论习题解答练习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是起始状态5）F1={q2}精品-可编辑-M2=(Q2,Σ,δ2,q2,F2)其中1）Q2={q1,q2,q3,q4};2）Σ={a,b};3）δ2为：abq1q2q3q4q1q2q3q4q2q1q3q43）q2是起始状态4）F2={q1,q4}1.3DFAM的形式描述为({q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。试画出此机器的状态图。1.6画出识别下述语言的DFA的状态图。a){w|w从1开始以0结束}q1q5q4q2q3uduuuudddd001110,10精品-可编辑-b){w|w至少有3个1}c){w|w含有子串0101}d){w|w的长度不小于3，且第三个符号为0}e){w|w从0开始且为奇长度，或从1开始且为偶长度}或f){w|w不含子串110}g){w|w的长度不超过5}0100110,10,1100110100,100,10,1110,100,10,10,100,110,100,110,10101100,10,10,10,10,10,10,1精品-可编辑-h){w|w是除11和111以外的任何字符}i){w|w的奇位置均为1}j){w|w至少含有2个0，且至多含有1个1}k){ε,0}l){w|w含有偶数个0，或恰好两个1}m)空集n)除空串外的所有字符串1110,10000010011111000,100,10,11100,10,11100111110000001精品-可编辑-1.7给出识别下述语言的NFA，且要求符合规定的状态数。a.{w|w以00结束}，三个状态b.语言｛w|w含有子串0101，即对某个x和y，w=x0101y｝，5个状态.c.语言｛w|w含有偶数个0或恰好两个1｝，6个状态。d.语言｛0｝，2个状态。e.语言0*1*0*0，3个状态。f.语言{ε}，1个状态。g.语言0*，1个状态。0,10,10,1000,1010,1010,101110100000010精品-可编辑-2.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。证明:设NFAM={Q，Σ,δ,q0,F}，F={ri1，……，rik}.添加一个状态p后，ri1，……，rik分别向p引ε箭头，将ri1，……，rik变为非接受状态，p变为接受状态。又因为添加ε箭头不影响NFA识别语言，所以命题成立。2.14a证明：设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},设ω=ω1ω2…ωn是字母表上任意字符串，因为M与N均为DFA,所以必然存在Q中状态序列r0,r1,…,rn,使得：r0=q0,δ(ri,ωi+1)=ri+1,i=0,…,n-11)若rnF则ωB;2)若rnF,则rnQ-F,即N接受ω，若ωB,所以N接受B的补集，即B的补集正则。所以，正则语言类在补运算下封闭。b.设B为{0}。NFAM：可识别它。依题对它作变换，得到N：则N识别的语言{ε}不是B的子集。所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。000精品-可编辑-但是由于NFA识别的语言类与DFA识别的语言类相同，即正则语言类。由a的证明，正则语言类在补运算封闭，可知，NFA识别的语言类---正则语言类在补运算下封闭。若NFA识别语言A，必有等价的DFA识别A,从而由a知，可交换DFA的接受与非接受状态构造识别A的补集的DFA,则必有等价的NFA识别A的补集。只是，该NFA未必有原NFA交换接受与非接受状态构造而成。1.15给出一个反例，说明下述构造不能证明定理2.24，即正则语言类在星号运算下封闭。设N=（Q1,Σ,δ1,q1,F1）识别A1。如下构造N=（Q1,Σ,δ1,q1,F1）。N应该识别A1*。a.N的状态集是N1的状态集。b.N的起始状态是N1的起始状态相同。c.F=｛q1｝∪F1。F的接受状态是原来的接受状态加上它的起始状态。d.定义δ如下：对每一个q属于Q和每一个a属于Σ。解：设N1识别语言A={至少含有一个1}，其中输入字母表为{0，1}，可知A*={空串或至少含有一个1}。N1:N:按上述规定构造N的状态图如上。可以看出L(N)={0,1}*不等于A*.所以如此构造的N不一定识别A*.1.16使用定理2.19中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。aFqqaqaFqaqaq},{),(),,(),(11111且若或若10,10,110,10,1a,bab12aa,bba123精品-可编辑-a)，b)，解：a),b)2.13给出生成练习2.4中语言的正则表达式。(注:答案不唯一)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)*1*.g.{w|w的长度不超过5}ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ.h.{w|w是除11和111以外的任何字符}0Σ*10Σ*110Σ*111ΣΣ*.i.{w|w的奇位置均为1}(1Σ)*(1).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.除空串外的所有字符串ΣΣ*.a,bab12b12aa,baab123b123aba,b精品-可编辑-1.19对下述每一个语言，给出4个字符串，2个是这个语言的成员，2个不是这个语言的成员。这里假设字母表Σ={a,b}.a.a*b*成员：ab，aab非成员：aba，bab.a(ba)*成员：ab，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.(a)b成员：b，ab非成员：a，bbh.(ababb)Σ*成员：a，bb非成员：，b1.21使用引理2.32中叙述的过程，把图2-38中的有穷自动机转换成正则表达式。a),b),解:a)a*b(aba*b)*b)(ab)a*b[(aaabb)a*b]*(a).(注：答案不唯一)1.29利用泵引理证明下述语言不是正则的。a.A1={0n1n2n|n0}。bab12abba,baa123精品-可编辑-证明：假设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={|w{a,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的长度都应是2的幂.而且xyi+1z的长度应是xyiz的长度的2n倍(n1)。于是可以选择足够大的i，使得|xyiz|=2np.但是|xyi+1z|-|xyiz|=|y|p.即|xyi+1z|2n+1,矛盾。∴A3不是正则的。1.30下面“证明”0*1*不是正则语言，指出这个“证明”中的错误。(因为0*1*是正则的，所以一定错误。)精品-可编辑-采用反证法证明。假设0*1*是正则的。令P是泵引定理给出的关于0*1*的泵长度。取S为字符串0p1p。S是0*1*的一个成员，但是例2.38已证明S不能被抽取。于是得到矛盾，所以0*1*不是正则的。解：在例2.38中的语言是{0n1n|n0}，取S为字符串0p1p，S确实不能被抽取；但针对语言0*1*，S是能被抽取的。将S分成三段S=xyz，由泵引理的条件3，y仅包含0，而xyiz属于语言0*1*，即S能被抽取，故题设中的“证明”不正确。1.24有穷状态转换器(FST)是确定性有穷自动机的一种类型。它的输出是一个字符串，而不仅仅是接受或拒绝。图2—39是两台有穷状态状态转换器T1和T2的状态图。T1T2FST的每一个转移用两个符号标记，一个指明该转移的输入符号，另一个指明输出符号。两个符号之间用斜杠“/”把它们分开。在T1中，从q1到q2的转移有输入符号2和输出符号1。某些转移可能有多对输入-输出，比如T1中从q1到它自身的转移。FST在对输入串w计算时，从起始状态开始，一个接一个地取输入符号w1wn，并且比照输入标记和符号序列w1wn=w进行转移。每一次沿一个转移走一步，输出对应的输出符号。例如，对输入2212011，机器T1依次进入状态q1,q2,q2,q2,q2,q1,q1,q1和输出1111000。对输入abbb，T2输出1001。给出在下述每一小题中机器进入的状态序列和产生的输出。a.T1对输入串011,输出：000,状态序列：q1,q1,q1,q1.b.T1对输入串211,输出：111,状态序列：q1,q2,q2,q2.c.T1对输入串0202,输出：0101,状态序列：q1,q1,q2,q1,q2。d.T2对输入串b,输出：1,状态序列：q1,q3.e.T2对输入串bbab,输出：1111,状态序列：q1,q3,q2,q3,q2.2/10/01/00/0q1q21/12/1b/1a/0q3q2q1b/0a/1b/1a/1精品-可编辑-f.T2对输入串bbbbbb,输出：110110,状态序列：q1,q3,q2,q1,q3,q2,q1。g.T2对输入串,输出：,状态序列：q1。1.25给出有穷状态转换器的形式定义。解：有穷状态转换器FST是一个五元组(Q,Σ,Г,δ,q0)1)Q是一个由穷集合，叫做状态集2)Σ是一个由穷集合，叫做输入字母表3)Г是一个由穷集合，叫做输出字母表4)δ：Q×ΣQ×Г是转移函数5)q0是起始状态FST计算的形式定义：M=(Q,Σ,Г,δ,q0)是一台由穷状态转换器，w=w1w2wn是输入字母表上的一个字符串。若存在Q中的状态序列：r0,r1,rn和输出字