計(jì)算理論習(xí)題解答

1、精品計(jì)算理論習(xí)題解答練習(xí)1.1 圖給出兩臺(tái)DFA M 1和M 2的狀態(tài)圖.回答下述有關(guān)問題.a. M 1的起始狀態(tài)是q 1b. M 1的接受狀態(tài)集是q2c. M 2的起始狀態(tài)是 q 1d. M 2的接受狀態(tài)集是 q1, q4e.對(duì)輸入aabb,M 1經(jīng)過的狀態(tài)序列是 q 1 , q2, q3, q 1, q 1f. M 1接受字符串a(chǎn)abb嗎？否g. M 2接受字符串&嗎？是1.2 給出練習(xí)2.1中畫出的機(jī)器 M1和M2的形式描述.M 1=(Q 1R81,q1,F1)其中1) Q1=q 1,q2,q3,;2)當(dāng)a,b；3) 81 為：a bq1q2q3q2q1q3q3q2q14) q1

2、是起始狀態(tài)5) F1=q 2M 2 =(Q 2,N §2,q 2,F2)其中1) Q2=q 1,q2,q3,q4;2) 2=a,b；3) 82 為：abq1q1q2q2q3q4q3q2q1q4q3q43) q2是起始狀態(tài)4) F2=q 1,q4試畫出此1.3 DFA M 的形式描述為 (qi, q2, q3, q4, q5, u,d, S,q3, q3),其中在表 2-3 中給出。機(jī)器的狀態(tài)圖。一10，1-可編輯-1.6畫出識(shí)別下述語言的 DFA的狀態(tài)圖。a)w | w 從1開始以0結(jié)束精品-可編輯-100,1j） w | w 至少含有2個(gè)0,且至多含有1個(gè)1k) 刈m）空集n）除空

3、串外的所有字符串0,10,1.7給出識(shí)別下述語言的 NFA ,且要求符合規(guī)定的狀態(tài)數(shù)。a. w | w 以00結(jié)束,三個(gè)狀態(tài)0,1b.語言 w | w 含有子串0101 ,即對(duì)某個(gè) x和y, w=x0101y c.語言 w | w含有偶數(shù)個(gè)0或恰好兩個(gè)1 , 6個(gè)狀態(tài)。d.語言 0, 2個(gè)狀態(tài)。e.語言0*1*0*0, 3個(gè)狀態(tài)。f.語百4,g.語言0*, 1個(gè)狀態(tài)。2.11 證明每一臺(tái)NFA都能夠轉(zhuǎn)換成等價(jià)的只有一個(gè)接受狀態(tài)的NFA。證明:設(shè)NFA M=Q , 2 ,q0,F, F=r ii,，rik.添加一個(gè)狀態(tài)p后，rii,，rik分別向p弓屋箭頭，將rii,，rik變?yōu)榉墙邮軤顟B(tài)，p變

4、為接受狀態(tài)。又因?yàn)樘砑?#163;箭頭不影響 NFA識(shí)別語言，所以命題成立。2.14 a證明：設(shè)M是一臺(tái)語言B的DFA,交換M的接狀態(tài)與非接受狀態(tài)得到一臺(tái)新的DFA ,則這臺(tái)新的DFA是識(shí)別B的補(bǔ)集，因此，正則語言類受在補(bǔ)運(yùn)算下封閉。b舉例說明：設(shè)M是一臺(tái)識(shí)別語言 B的NFA ,交換M的接受狀態(tài)與非接受狀態(tài)得到一臺(tái)新的NFA ,這臺(tái)新的NFA不一定識(shí)別B的補(bǔ)集。NFA識(shí)別的語言類在補(bǔ)集下封閉嗎？解釋你的回答。解：a. M是DFA, M是Q,M 對(duì)所，令N=Q,乙8,q0,Q-F,設(shè)w= coi 323n是字母表上任意字符串，因?yàn)镸與N均為DFA,所以必然存在 Q中狀態(tài)序列r0,r1,nr使得：

5、r0=q 0, 8（口，wi+1 ）=r i+1 , i=0,n-11）若 rn F 則 3 B;2）若rn F則rn Q-F,即N接受，若co B,所以N接受B的補(bǔ)集，即B的補(bǔ)集正則。所以，正則語言類在補(bǔ)運(yùn)算下封閉。b.設(shè) B 為0。NFA M :可識(shí)別它。依題對(duì)它作變換，得到N :則N識(shí)別的語言 *不是B的子集。所以交換 M的接受狀態(tài)與非接受狀態(tài)得到的新的NFA不一定 識(shí)別B的補(bǔ)集。精品但是由于NFA識(shí)別的語言類與 DFA識(shí)別的語言類相同，即正則語言類。由a的證明，正則語言類在補(bǔ)運(yùn)算封閉，可知，NFA識(shí)別的語言類-正則語言類在補(bǔ)運(yùn)算下封閉。若NFA識(shí)別語言A,必有等價(jià)的DFA識(shí)別A,從而由

6、a知，可交換DFA的接受與非接受狀態(tài)構(gòu)造 識(shí)別A的補(bǔ)集的DFA,則必有等價(jià)的NFA識(shí)別A的補(bǔ)集。只是，該NFA未必有原NFA交換接受與 非接受狀態(tài)構(gòu)造而成。1.15 給出一個(gè)反例，說明下述構(gòu)造不能證明定理2.24,即正則語言類在星號(hào)運(yùn)算下封閉。設(shè) N= (Qi, 2,Si,qi,Fi)識(shí)別 Ai。如下構(gòu)造 N= (Qi, "Si,qi,Fi)。N 應(yīng)該識(shí)別 Ai*。a. N的狀態(tài)集是Ni的狀態(tài)集。b. N的起始狀態(tài)是Ni的起始狀態(tài)相同。c. F= qi UFi。F的接受狀態(tài)是原來的接受狀態(tài)加上它的起始狀態(tài)。(q,a)i(q,a), 若q F1或 a i(q,a) q,若q Fi 且

7、ad.定義8如下：對(duì)每一個(gè) q屬于Q和每一個(gè)a屬于2解：設(shè)Ni識(shí)別語言A=至少含有一個(gè)i,其中輸入字母表為0, i,可知A*=空串或至少含有一個(gè)i。Ni:N:按上述規(guī)定構(gòu)造 N的狀態(tài)圖如上?？梢钥闯?L(N)=0,i *不等于A*.所以如此構(gòu)造的 N不一定識(shí)別A*.1.16 使用定理2.i9中給出的構(gòu)造，把下圖中的兩臺(tái)非確定型有窮自動(dòng)機(jī)轉(zhuǎn)換成等價(jià)的確定型有窮自動(dòng)機(jī)。精品n.除空串外的所有字符串2 £-可編輯-a),b)解：a),b)2.13 給出生成練習(xí) 2.4中語言的正則表達(dá)式。(注：答案不唯一)a. w| w從1開始以0結(jié)束 1 2*0.b. w| w至少有 3 個(gè) 1 

8、3;l £1 £11.c. w| w含有子串 0101 £0101 £.d. w| w的長(zhǎng)度不小于 3,且第三個(gè)符號(hào)為02十£.e. w| w從0開始且為奇長(zhǎng)度，或從1開始且為偶長(zhǎng)度0( 2E 1式2 1.f. w| w不含子串 110 (010)*1*.g. w| w的長(zhǎng)度不超過 52H2h. w | w 是除11和111以外的任何字符 0 2* 10 £ 110 £ 111 2七i. w | w 的奇位置均為 1 (14*(1).j. w | w 至少含有 2個(gè)0,且至多含有 1個(gè)1 0 *(00 010001100)

9、0k. £,0. £ 0.l. w | w 含有偶數(shù)個(gè)0.或恰好兩個(gè)1(1 *01 *0)*1* 0*10*10*.m. 空集.精品-可編輯-1.19對(duì)下述每一個(gè)語言，給出4個(gè)字符串,個(gè)是這個(gè)語言的成員，2個(gè)不是這個(gè)語言的成員。這里假設(shè)子母表2=a,b.1.21使用引理2.32中敘述的過程，把圖2-38a)，b)，中的有窮自動(dòng)機(jī)轉(zhuǎn)換成正則表達(dá)式O解:a) a*b(a ba*b)*b)(ab)a b(aa ab b)a b (a).a. a*b*成員：ab ,aab非成員：aba , bab. a(ba)*成員：ab ,abab非成員：abb , aac. a* b*成員：a

10、aa,bbb非成員：ab , bad. (aaa)*成員：aaa,aaaaaa非成員：a, aa* *. * *e. Sa Sb Sa S成員：aba,aaba非成員：aa, abbf. ababab成員：aba,bab非成員：a, bg.(a)b成員:b,ab非成員：a, bbh. (a ba bb)2*成員：a, bb非成員：，b（注：答案不唯一）1.29利用泵引理證明下述語言不是正則的。a. A1=0 n1n2n | n 0。精品證明：假設(shè) Ai是正則的。設(shè)p是泵引理給出的關(guān)于 Ai的泵長(zhǎng)度。令 S=0P1P2p,.S是Ai的一個(gè)成員且 S的長(zhǎng)度大于p,所以泵引理保證 S可被分成3段$=

11、乂丫2且滿足泵引理的3個(gè)條件。根據(jù)條件3, y中只含0, xyyz中，。比1、2多，xyyz不是Ai的成員。違反泵引理的 條件1 ,矛盾。. Ai不是正則的。b. A 2=www | wa,b *.證明：假設(shè) A2是正則的。設(shè)p是泵引理給出的關(guān)于 A2的泵長(zhǎng)度。令 S=a pba pba pb,.S是A2的一個(gè)成員且S的長(zhǎng)度大于p,所以泵引理保證 S可被分成3段$=乂丫2且滿足泵引理的3個(gè)條件。根據(jù)條件3, y中只含a,所以xyyz中第一個(gè)a的個(gè)數(shù)將比后兩個(gè) a的個(gè)數(shù)多，故xyyz 不是A2的成員。違反泵引理的條件i ,矛盾。. A2不是正則的。c. A 3=a 2n | n 0.（在這里，a

12、2n 表示一串 2n 個(gè) a .）證明：假設(shè) A3是正則的。設(shè)p是泵引理給出的關(guān)于 A3的泵長(zhǎng)度。令 S= a 2p,.S是A2的一個(gè)成員且S的長(zhǎng)度大于p,所以泵引理保證 S可被分成3段$=乂丫2且滿足泵引理的3個(gè)條件。即對(duì)任意的i 0, xyiz都應(yīng)在A3中，且xyiz與xyi+i z的長(zhǎng)度都應(yīng)是2的哥.而且xyi+i z 的長(zhǎng)度應(yīng)是 xyiz的長(zhǎng)度的 2n倍（n i）。于是可以選擇足夠大的i,使得|xyiz|=2 n>p.但是|xyi+i z|-|xy iz|=|y| p.即 |xyi+iz|<2 n+i ,矛盾。. A3不是正則的。i.30下面“證明” 0T不是正則語言，指出

13、這個(gè)“證明”中的錯(cuò)誤。 （因?yàn)?T是正則的，所以一定錯(cuò)誤。）-可編輯-精品采用反證法證明。假設(shè) 0*1*是正則的。令 P是泵引定理給出的關(guān)于 0*1*的泵長(zhǎng)度。取S為字符串0P1Pos是0*1*的一個(gè)成員，但是例 2.38已證明S不能被抽取。于是彳#到矛盾，所以0*1*不是正則的。解：在例2.38中的語言是0n1n | n 0,取S為字符串0Plp, S確實(shí)不能被抽?。坏槍?duì)語言0*1*,S是能被抽取的。將 S分成三段S=xyz ,由泵引理的條件 3, y僅包含0,而xyiz屬于語言0*1*, 即S能被抽取，故題設(shè)中的“證明”不正確。1.24有窮狀態(tài)轉(zhuǎn)換器（FST）是確定性有窮自動(dòng)機(jī)的一種類型

14、。它的輸出是一個(gè)字符串，而不僅僅是接受或拒絕。圖2 39是兩臺(tái)有窮狀態(tài)狀態(tài)轉(zhuǎn)換器T1T2FST的每一個(gè)轉(zhuǎn)移用兩個(gè)符號(hào)標(biāo)記，一個(gè)指明該轉(zhuǎn)移的輸入符號(hào)，另一個(gè)指明輸出符號(hào)。兩個(gè)符號(hào)之間用斜杠“ /”把它們分開。在 T1中，從q1到q2的轉(zhuǎn)移有輸入符號(hào) 2和輸出符號(hào)1。某些轉(zhuǎn)移可能有多對(duì)輸入-輸出，比如T1中從q1到它自身的轉(zhuǎn)移。FST在對(duì)輸入串w計(jì)算時(shí)，從起始狀態(tài)開始，一個(gè)接一個(gè)地取輸入符號(hào) W1 wn,并且比照輸入標(biāo)記和符號(hào)序列W1 wn=w進(jìn)行轉(zhuǎn)移。每一次沿一個(gè)轉(zhuǎn)移走一步，輸出對(duì)應(yīng)的輸出符號(hào)。例如，對(duì)輸入2212011 ，機(jī)器T1依次進(jìn)入狀態(tài)q1，q 2, q 2, q 2, q2, q 1,

15、 q 1, q 1和輸出1111000 。對(duì)輸入abbb , T2輸出1001 。給出在下述每一小題中機(jī)器進(jìn)入的狀態(tài)序列和產(chǎn)生的輸出。a. T1對(duì)輸入串011,輸出：000,狀態(tài)序列：q1, q1, q1, q1.b. T1對(duì)輸入串211,輸出：111,狀態(tài)序列：q1, q2, q2, q2.c. T1 對(duì)輸入串 0202,輸出：0101,狀態(tài)序列：q1, q 1, q2, q1, q2od. T2對(duì)輸入串b,輸出：1,狀態(tài)序列：q1, q3.e. T2對(duì)輸入串 bbab,輸出：1111,狀態(tài)序列：q 1, q 3, q 2, q 3, q2.f.T2 對(duì)輸入串 bbbbbb, 輸出：1101

16、10, 狀態(tài)序列：qi, q 3, q2, qi, q 3, q 2, qi。g. T2對(duì)輸入串，輸出：，狀態(tài)序列：q1o1.25給出有窮狀態(tài)轉(zhuǎn)換器的形式定義。解：有窮狀態(tài)轉(zhuǎn)換器FST是一個(gè)五元組(Q,N1,8,q0)1) Q是一個(gè)由窮集合，叫做狀態(tài)集2) 2是一個(gè)由窮集合，叫做輸入字母表3) P是一個(gè)由窮集合，叫做輸出字母表4) S:QXN QXP是轉(zhuǎn)移函數(shù)5) qo是起始狀態(tài)FST計(jì)算的形式定義：M=(Q, NlS.qo)是一臺(tái)由窮狀態(tài)轉(zhuǎn)換器，w=w 1W2 w n是輸入字母表上的一個(gè)字符串。若存在 Q中的狀態(tài)序列：ro, r1,rn和輸出字母表上的一個(gè)字符串s=s vsn,滿足下述條件：

17、1) ro=q 0;2) 8(門,Wi+1 )=(r i+1 , Si+1), i=0,1,n-1則M在W的輸入下輸出s.1.26 利用你給練習(xí)2.20的答案，給出練習(xí) 2.19中畫出的機(jī)器T1和T2的形式描述。解：有窮狀態(tài)轉(zhuǎn)換器 Ti的形式描述為:T1=(q 1, q2 , 0 , 1 , 2, 6, q1, 0,1)其中轉(zhuǎn)移函數(shù)為:012q1q 1/0q 1/0q2/1q2q1/0q2/1q2/1有窮狀態(tài)轉(zhuǎn)換器T2的形式描述為：T2=(q 1, q2, q3, a, b, 6, qi, 0,1)其中轉(zhuǎn)移函數(shù)為：abq1q2/1q3/1q2q3/1q 1/0q3q1/0q2/11.27 給出

18、一臺(tái)具有下述行為的FST的狀態(tài)圖。它的輸入、輸出字母表都是0,1。它輸出的字符串與輸入的字符串偶數(shù)為相同、奇數(shù)位相反。例如，對(duì)于輸入0000111 ,它應(yīng)該輸出1010010 。解：1/01/10/01.46 證明：a)假設(shè)0n1m0n|m,n >0是正則的，p是由泵引理給出的泵長(zhǎng)度。取 s=0P1q0P, q>0 。由泵引理?xiàng)l件 3知，|xy|Wp,故y 一定由0組成，從而字符串xyyz中1前后0的數(shù)目不同，即xyyz不屬于該語言， 這與泵引理矛盾。所以該語言不是正則的。b)假設(shè)0n1n|n>0的補(bǔ)集是正則的，則根據(jù)正則語言在補(bǔ)運(yùn)算下封閉可得0n1n|n>0是正則的，

19、這與已知矛盾，故假設(shè)不成立。所以該語言不是正則的。記 c=0 m1n|mwn, ic 為 c 的補(bǔ)集，r c A0*1*=0 n1n|n 0,已知0n1n|nR不是正則的。若.c 是正則的，由于 0*1*是正則的，那么cA0*1*也應(yīng)為正則的。這與已知矛盾，所以 .c不是正則的。由正則語言在補(bǔ)運(yùn)算下的封閉性可知c也不是正則的。-可編輯-c) w | w0,1*不是一個(gè)回文的補(bǔ)集是w | w0,1*是一個(gè)回文，設(shè)其是正則的，令p是由泵引理給出的泵長(zhǎng)度。取字符串 s=0P1q0P,顯然s是一個(gè)回文且長(zhǎng)度大于 p。由泵引理?xiàng)l件 3知|xy| Wp,故y 只能由0組成。而xyyz不再是一個(gè)回文，這與泵

20、引理矛盾。所以 w | w 0,1*是一個(gè)回文不是正則 的。由正則語言在補(bǔ)運(yùn)算下的封閉性可知w | w 0,1*不是一個(gè)回文也不是正則的。1.31對(duì)于任意的字符串 w=w 1w23wn, w的反轉(zhuǎn)是按相反的順序排列w得到的字符串，記作 wR,即wR=wnw2w1。對(duì)于任意的語言 A ,記 AR=w R | A證明：如果 A是正則的，則 AR也是正則的。證明：因?yàn)锳是正則語言，所以可以用NFA來表示該語言，現(xiàn)在來構(gòu)造AR的NFA,將NFA A中的接受態(tài)變?yōu)橹虚g態(tài)，起始態(tài)變?yōu)榻邮軕B(tài)，再添加一新的起始態(tài)，并用e箭頭連接至原來的接受態(tài)，其它所有的箭頭反向。 經(jīng)過變換后得到 NFA變成描述AR的NFA.

21、1.32 令'1 I1L1 J J3包括所有高度為 3的0和1的列向量。3上的字符串給出三行 0和1的字符串。把每一行看作一個(gè)二進(jìn)制數(shù)，令B= w 3* | w最下面一行等于上面兩行的和 例如，0、0r01,證明B是正則的。證明：由題設(shè)B的定義可知，w上面兩行之和減去下面一行結(jié)果為零，由此可設(shè)計(jì)NFA M (Q, N 8, q0, F),其中 =3。Q=q 0,q1。q。狀態(tài)表示上一次運(yùn)算的進(jìn)位為0, q 1狀態(tài)表示上一次運(yùn)算的進(jìn)位為1。所以可知自動(dòng)機(jī)M識(shí)別的是語言BR,因此BR是正則的。由題2-24的結(jié)論可知 B也是正則的。2包含所有高度為 2的0和1的列。證明：如下的NFA識(shí)別CR

22、：,中1q 0狀本率卜上一次運(yùn)算的進(jìn)位為態(tài)壽示0,1.33 令2上的字符串名出兩行 0和1的字符串。把每一行看作一個(gè)二進(jìn)制數(shù)，令C= w 2* | w下面一行等于上面一行的3倍。證明C是正則的?？梢约僭O(shè)已知問題2.24中的結(jié)果。q 1狀態(tài)表示上一次運(yùn)算的進(jìn)位為1, q 2狀態(tài)表示上一次運(yùn)算的進(jìn)位為2。如下的的數(shù)的3倍余0,1,2的情況。1.34 令2包含所有高度為 2的0和1的列。2上的字符串名出兩行 0和1的字符串。把每一行看作一個(gè)二進(jìn)制數(shù)，令D= w 2* | w上一行大于下一行。證明D是正則的。證明：由題設(shè)可設(shè)計(jì)自動(dòng)機(jī)M=(Q, " 8, q, F),其中Q=q 1 ,q2,

23、F=q 2,轉(zhuǎn)移函數(shù)與狀態(tài)圖為：00011011q1q1q2q 1q2q2q2q2q 21.35 設(shè)匯2與問題2.26中的相同。把每一行看作 0和1的字符串，令 E=w 2* | w的下一行是上一行的反轉(zhuǎn),證明E不是正則的。證明：假設(shè)E是正則咯，令 J是有泵引理給出的泵長(zhǎng)度。'i 1 0 pN J11.選擇字符串s=。于是s能夠被劃分為xyz且滿足泵引理的條件。1 根據(jù)條件3, y僅能取包含 04部分，當(dāng)添加一個(gè)y時(shí)，xyyz不屬于E.所以E不是正則的.1.36 令Bn=a k | k是n的整數(shù)倍。證明對(duì)于每一個(gè) n 1, Bn是正則的。證明：設(shè)字母表匯為a,則an是一正則表達(dá)式。所以

24、，(an)*也是正則表達(dá)式。由題意Bn=(an)*,即Bn可以用正則表達(dá)式表示。所以，Bn也是正則的。1.37 令Cn=x | x是一個(gè)二進(jìn)制數(shù)，且是n的整數(shù)倍。證明對(duì)于每一個(gè)n 1, Cn是正則的。證明：下面的 DFA識(shí)別Cn：(正向讀)M=( Q, 0,1 , q0 , F ),其中 Q = 0,1,2,，n-1,(i,(1) i+1 mod n, ( i,0 )=( 2i mod n), i=0,1,2,，n-1,起始狀態(tài)為0, F = 0.這里i表示當(dāng)前數(shù) mod n余i.下面的DFA識(shí)另ij CnR：(反向讀)M=( Q, 0,1 , q。, F )，其中 Q = (i,j)|i,j

25、=0,1,2,，n-1,(i,j),1)=( 2i mod n, (2i+j)mod n ),(i,j),0)=( 2i mod n, j ), i,j=0,1,2,，n-1起始狀態(tài)為(1,0), F = (i,0) | i=0,1,，n-1.這里(i,j)表示當(dāng)前數(shù) mod n余j,而下一位所表示單位數(shù)mod n余i(例如，若讀下一位將達(dá)到k位,則下一位所表示單位數(shù)為10 k-1).1.38 考慮一種叫做全路徑 NFA的新型有窮自動(dòng)機(jī)。一臺(tái)全路徑 NFA M 是5元組(Q, , , q 0, F).如 果M對(duì)x*的每一個(gè)可能的計(jì)算都結(jié)束在 F中的狀態(tài)，則M接受x。注意，相反的，普通的 NFA

26、只需有一個(gè)計(jì)算結(jié)束在接受狀態(tài)，就接受這個(gè)字符串。證明：全路徑NFA識(shí)別正則語言。證明：一個(gè)DFA 一定是一個(gè)全路徑 NFA。所以下面只需證明，任意全路徑NFA ,都有一個(gè)與之等價(jià)的 DFA。設(shè)有一全路徑 NFA N=( Q, RS, qo, F),構(gòu)造一個(gè)新與 N等價(jià)的全路徑 NFA/(q,a) ,q s,且 S(q,a)s,q s,且 S(q,a)=Ni = ( Qi, N Si, qo, F),其中 Qi=Q s, s Q。對(duì)于任意 q Qi, a 281(q,a)=s,q=s.現(xiàn)在來構(gòu)造一個(gè)與全路徑NFA N i等價(jià)的DFA M = (Q2, N泗q 1, F2).其中1) Q 2=Po

27、wer(Q 1),即Qi的所有子集組成的集合(也即Qi的募集)；2)定義函數(shù)E: Q2 Q2為：對(duì)任意R Q2, E(R) . i(r,); r R3) q i=E(q 0);4)對(duì)于任意的R屬于Q2, a屬于"2(R,a) E i(r,a). r R5) F2= R Q2 | R F。綜上所述，DFA等價(jià)于全路徑NFA。i.40如果存在字符串z使得xz=y,則稱字符串x是字符串y的前綴。如果x是y的前綴且xwy,則稱x是y的真前綴。下面每小題定義一個(gè)語言A上的運(yùn)算。證明：正則語言類在每個(gè)運(yùn)算下封閉。a) NOPREFIX(A)= 3 C A| 3的任意真前綴都不是 A的元素b)NO

28、EXTEND(A)= 3 C A| 3不是A中任何字符串的真前綴 證明：假設(shè)DFA M=( Q, N 8, q 0, F)識(shí)別語言 A。a)構(gòu)造 NFA N i=( Q, " Si, qo, F)識(shí)別語言 NOPREFIX(A)。其中， (q,a), q Q F,a ；對(duì)任意 q F, a 2 , i(q,a),q F ；, q Q,a ;所以，即NOPREFIX(A)為正則語言，亦即正則語言類A在NOPREFIX(A)運(yùn)算下封閉。b)構(gòu)造 NFA N 2=( Q, N 8, qo,F2)識(shí)別語言 NOEXTEND(A) 。 F2 構(gòu)造如下：對(duì)M中的任一接受狀態(tài) qi,若存在一條從它

29、出發(fā)到達(dá)某接受狀態(tài)(含本身)的路徑，則將狀態(tài) qi改為非接受狀態(tài)；最后剩下的接受狀態(tài)集記為F2.所得的 NFA N2即識(shí)別 NOEXTEND(A)。所以，NOEXTEND(A)為正則語言，亦即正則語言類A在運(yùn)算NOEXTEND(A)下封閉。1.48證明：構(gòu)造NFA N如下：0由于該NFA識(shí)別D,故D是正則語言。1.50 參見練習(xí)1.24中給出的有窮狀態(tài)轉(zhuǎn)換器的非形式定義。證明不存在FST對(duì)每一個(gè)輸入 w能夠輸出wR,其中輸入和輸出的字母表為 0,1。證明：假設(shè)存在一臺(tái) FST對(duì)每個(gè)輸入w能夠輸出wRo則對(duì)于輸入串 W1=100, w 2=101.該FST可分別輸出w1R=001 , W2r=1

30、01 ,于是對(duì)于它的起始狀態(tài)和輸入字符1,會(huì)輸出1和0兩個(gè)不同字符，這與 FST是確定性有窮自動(dòng)機(jī)相矛盾。所以，不存在一臺(tái) FST對(duì)每個(gè)輸入w能夠輸出wR。1.51證明：1)自反性。即對(duì)任意字符串x, x LX。這是因?yàn)閷?duì)于每個(gè)字符串z均有xz和xz同時(shí)是或不是L的成員。2)對(duì)稱性。即對(duì)任意字符串x和y,若xLy,則ylx。這是因?yàn)槿魓Ly,則對(duì)于每個(gè)字符串z, xz和yz同時(shí)是或不是L的成員，那么yz和xz同時(shí)是或不是L的成員，于是y lx。3)傳遞性。即對(duì)任意字符串x,y和z,若x Ly且y lz,則x lz。這是因?yàn)閷?duì)任意字符串u,由x Ly知xu和yu同時(shí)是或不是 L的成員，由y lz

31、知yu和zu同時(shí)是或不是L的成員，所以xu 和zu同時(shí)是或不是L的成員，此即x lz。綜上所述， L是自反的，對(duì)稱的，傳遞的，所以是一個(gè)等價(jià)的關(guān)系。1.53 令方0 , 1 , + , =和ADD= x=y+z | x,y,z是二進(jìn)制整數(shù)，且 x是y與z的和證明ADD不是正則的。證明：假設(shè)ADD是正則白勺。設(shè) P是泵引理給出的關(guān)于 ADD的泵長(zhǎng)度。令s為1P=10 P-1+1 P-1。于是s能 夠被劃分成xyz ,且滿足泵引理的條件。根據(jù)條件3, y=1 i, i>0.所以xyyz為 1P+i=10 P-1+1 P-1 add。故 ADD 不是正則的。1.54 證明：語言F=a ibjc

32、k | i,j,k 0且若i=1 ,則j=k滿足泵引理的3個(gè)條件，雖然它不是正則的。解釋 這個(gè)事實(shí)為什么與泵引理不矛盾。證明：對(duì)任意正數(shù) p>1 ,設(shè)S是F中的一個(gè)成員且 S的長(zhǎng)度不小于 p。將S分成3段S=xyz。(1) i=0 , j=0.此時(shí) S=ck(k>0)。取 x= , y=c, z=c k-1 .則對(duì)任意 i 0, xy iz F。(2) i=0 , j>0.此時(shí) S=b jck(j>0, k 0).取 x= , y=b, z=b j-1 ck.則對(duì)任意 i 0, xy iz F。(3) i=1.此時(shí) S=ab jck(j 0, k 0).取 x= , y

33、=a, z=b jck.則對(duì)任意 i 0, xy iz F。(4) i=2.此時(shí) S= a2bjck(j 0, k 0).取 x= , y=a 2, z=b jck.則對(duì)任意 i 0, xy iz F。(5) i>2.此時(shí) S= a ibjck(i 3, j 0, k 0).取 x= , y=a, z=a i-1bjck.則對(duì)任意 i 0, xy iz F。綜上所述，語言F滿足泵引理的3個(gè)條件。這一事實(shí)不與泵引理矛盾是因?yàn)楸靡硎钦齽t語言的必要不充 分條件。1.55 求最小泵長(zhǎng)度。a. 0001 *的最小泵長(zhǎng)度為4.因?yàn)閷?duì)任何s若|s|=3則s只含有0,不能被抽取。若|s|>4時(shí)，

34、把s劃分為x=000 y=1 z為其余部分，則 xy iz 0001 *。b. 0*1*最小泵長(zhǎng)度為1.若同對(duì)時(shí),S分兩種情況：1. S以0開頭，令x=, y=0, z為其余則xyiz0*1 *.2. S以1開頭，令x=, y=1, z為其余則xyiz0*1 *.c. (01) *最小泵長(zhǎng)度為2.若 |s|>2 時(shí)，令 x= , y=01, z 為其余，則 xyiz (01) *.d. 01 ,其最小泵長(zhǎng)度為 3。因?yàn)檎Z言中只有有限個(gè)字符串時(shí)，任何一個(gè)字符串都不能被抽取。所以有限語言的泵長(zhǎng)度為其最長(zhǎng)字符串的長(zhǎng)度加1。此時(shí)沒有比泵長(zhǎng)度長(zhǎng)的字符串，前提假所以命題真。e.,其最小泵長(zhǎng)度為1.理

35、由類似于d中所述。2.39 證明：設(shè)對(duì)于每一個(gè)k>1 ,Ak=w | w包含子串1k-11*,下面證明Ak能被一臺(tái)k個(gè)狀態(tài)的 DFA識(shí)別，而不能被只有k 1個(gè)狀態(tài)的 DFA識(shí)別。顯然，Ak能被k個(gè)狀態(tài)的DFAM=(q 1,q2,qk, 1, q1，qk).識(shí)別，其中 (qi,1)=q i21 (i=1,2，,k-1),(qk,1)=q 9假設(shè)A,可以被只有 k-1個(gè)狀態(tài)的 DFA Ml識(shí)別?？紤]這樣一個(gè)輸入串 s=1 k-1 ,設(shè) M 識(shí)另1J s的狀態(tài)序列是 r,已 由于 M 的狀態(tài)只有 k-1 個(gè)，根據(jù)鴿 巢原理，ri,r2,rk中必有兩個(gè)重復(fù)的狀態(tài)，假設(shè)是 r=rj (0 i<

36、;j k), 此時(shí)可知，字符串 x=1 j-i把 M 從ri 帶到了 rj。由于ri,rj是同一個(gè)狀態(tài)，所以去掉s中的x子串，M仍可識(shí)別s的剩余部分，即M識(shí)別1k-1-(i-i), 這與MiJ只另1J Ak 相矛盾。故 A不能被只有 k-1個(gè)狀態(tài)的 DFA M 識(shí)別。所以，對(duì)于每一個(gè) k>1 ,存在Ag 使得AK能被K個(gè)狀態(tài)的DFA識(shí)別，而不能被只有k-1個(gè)狀態(tài)的DFA識(shí)別。2.1 略。2.2 a.利用語言A=a mbncn | m,n 0和A=a nbncm | m,n 0以及例3.20 ,證明上下文無關(guān)語言在交 的運(yùn)算下不封閉。b.利用(a)和DeMorgan 律(定理1.10),證

37、明上下文無關(guān)語言在補(bǔ)運(yùn)算下不封閉。證明：a.先說明A,B均為上下文無關(guān)文法，對(duì) A構(gòu)造CFG CiS aS|T|T bTc|對(duì)B,構(gòu)造CFG C2 S Sc|R| R aRb由此知A,B均為上下文無關(guān)語言。但是由例3.20, A AB=a nbncn|n 0不是上下文無關(guān)語言，所以上下文無關(guān)語言在交的運(yùn)算下不封閉。b.用反證法。假設(shè) CFL在補(bǔ)運(yùn)算下封I< 則對(duì)于 中上下文無關(guān)語言 A,B, A,B也為CFL,且CFL對(duì)并 運(yùn)算封閉，所以A B也為CFL,進(jìn)而知道 A B為CFL,由DeMorgan 定律其 后=AAB,由此AAB 是CFL,這與（a）的結(jié)論矛盾，所以 CFL對(duì)補(bǔ)運(yùn)算不封

38、閉。2.3 略。PDA ,其中字母表 =0,1。2.4 和2.5給出產(chǎn)生下述語言的上下文無關(guān)文法和a. w | w至少含有3個(gè)1S-A1A1A1AA-0A|1A|b. w | w以相同的符號(hào)開始和結(jié)束 Sf0A0|1A1Af0A|1A|c. w | w的長(zhǎng)度為奇數(shù)Sf0A|1AA-0B|1B|0,1,Bf0A|1Ad. w | w的長(zhǎng)度為奇數(shù)且正中間的符號(hào)為0Sf0S0|1S1|0S1|1S0|0e.w | w中1比0多100,1f. w | w=w RSf0S0|1S1|1|00,00,0g.空集S-S2.6給出產(chǎn)生下述語言的上下文無關(guān)文法：a.字母表a,b上a的個(gè)數(shù)是b的個(gè)數(shù)的兩倍的所有字

39、符串組成的集合。S-bSaSaS|aSbSaS|aSaSbS|b .語言anbn|n 0的補(bǔ)集。見問題 3.25中的CFG:SfaSb|bY|T aTf aT|bT|c. w#x | w, x0,1 *且 wR 是 x 的子串。SfUVU f0U0|1U1|WW fW1|W0|#V f0V|1V|d. xi#x2# #xk|k 1,每一個(gè) xi a,b*,且存在 i 和 j 使得 xi= xjR。SfUVWU fA|A faA|bA|#A|#VfaVa|bVb|#B|#BfaB|bB|#B|#W fB|2.8證明上下文無關(guān)語言類在并，連接和星號(hào)三種正則運(yùn)算下封閉。a. A B方法一：CFG。設(shè)

40、有 CFG Gi = (Qi, ,Ri,Si)和 G2=(Q 2, ,R2,S2)且 L(Gi)=A, L(G2)=B。構(gòu)造 CFGG=(Q, ,R,S0),其中Q= Q 1 Q2 So, So 是起始變?cè)琑= RiR2 SoSi .方法二：PDA。設(shè) P1=(Q1, , 1, 1,q1,F1)識(shí)別 A, P2=(Q 1, , 2, 2,q2,F2)是識(shí)別 B。則如下構(gòu)造的P=(Q, , ,qo,F)識(shí)別A B,其中1) Q=Q i Q2 qo是狀態(tài)集，2) = i 2,是棧字母表，3) qo是起始狀態(tài)，4) F=Fi F2是接受狀態(tài)集，5) 是轉(zhuǎn)移函數(shù)，滿足對(duì)任意q Q, a ,b(qi,

41、 ),3, ),若q qo,a b ,i(q,a, b),若q Qi,b ( 1),(q,a,b)="2(q,a, b),右q Q2,b ( 2), ,else.b.連接AB方法一：CFG。設(shè)有 CFG Gi = (Qi, ,Ri,Si)和 G2=(Q 2, ,R2,S2)且 L(Gi)=A, L(G2)=B。構(gòu)造 CFGG=(Q,R,So),其中Q= Q 1 Q2 So, So 是起始變?cè)琑= Ri R2 SoS1S2.方法二：PDA。設(shè)Pi=(Q 1, , 1, i,qi,Fi)識(shí)別A, P2=(Q 1, , 2, 2,q2,F2)是識(shí)別B,而且Pi滿足在接受之前排空棧(即若進(jìn)

42、入接受狀態(tài)，則棧中為空)這個(gè)要求。則如下構(gòu)造的P=(Q, , ,qi,F)識(shí)別A B,其中1) Q=Q 1 Q2是狀態(tài)集，2) =12,是棧字母表，3) qi是起始狀態(tài)，4) F= Fi F2是接受狀態(tài)集，5) 是轉(zhuǎn)移函數(shù)，滿足對(duì)任意q Q, a ,bi(q,a,b),i(q,a,b)(q2, ),(q,a,b)=i(q,a, b),c.若 q QiFi,b ( 1)若 qFi,a b ,若q Fi,(a,b)(,),若q Q2,b ( 2),else2(q,a,b),方法一：CFG。設(shè)有 CFG Gi = (Qi,Ri,Si), L(Gi)=A。構(gòu)造 CFG G=(Q,R,S。)，其中 Q=

43、 Q 1 S。,So 是起始變?cè)?，R= Ri So SoSo|Si| .方法二：PDA。設(shè)Pi=(Qi, , 1, i,qi,Fi)識(shí)別A,而且Pi滿足在接受之前排空棧(即若進(jìn)入接受狀態(tài)，則棧中為空)這個(gè)要求。則如下構(gòu)造的P=(Q, , ,qi,F)識(shí)別A*,其中1) Q=Q 1 qo是狀態(tài)集,2) =1,是棧字母表，3) qo是起始狀態(tài),4) F= F1 qo是接受狀態(tài)集,若 q Q1F1,若 q F1,a b,若q F1,(a,b)(,),若 q qo,a b,5) 是轉(zhuǎn)移函數(shù)，滿足對(duì)任意q Q, a ,b1(q,a,b),1(q,a,b) (勺，),(q,a,b)=1(q,a,b),(q

44、1,)else2.9證明在3.1節(jié)開始部分給出的文法G2 中, 字符串 the girl touches the boy with the flower有兩個(gè)不同的最左派生，敘述這句話的兩個(gè)不同意思。句子< 名詞短語 >< 動(dòng)詞短語>< 復(fù)合名詞 >< 動(dòng)詞短語>< 冠詞 >< 名詞 >< 動(dòng)詞短語>a_<名詞 >< 動(dòng)詞短語>a_girl_<動(dòng)詞短語>a_girl_<復(fù)合名詞>a_girl_<動(dòng)詞 >< 名詞短語>a_girl_touch

45、es_<名詞短語 >a_girl_touches_<復(fù)合名詞 >< 介詞短語 >a_girl_touches_< 冠詞 >< 名詞 >< 介詞短語 >a_girl_touches_the_< 介詞 >< 復(fù)合名詞 >a_girl_touches_the_boy_<介詞短語 >a_girl_touches_the_boy_<介詞 >< 復(fù)合名詞 >a_girl_touches_the_boy_with_<復(fù)合名詞 >a_girl_touches_the_

46、boy_with_<冠詞 >< 名詞 >a girl touches the boy with the <名詞 >a girl touches the boy with the flower含義是：女孩碰這個(gè)帶著花的男孩<句子><名詞短語 >< 動(dòng)詞短語><復(fù)合名詞 >< 動(dòng)詞短語><冠詞 >< 名詞 >< 動(dòng)詞短語>a_<名詞 >< 動(dòng)詞短語>a_girl_<動(dòng)詞短語>a_girl_<復(fù)合動(dòng)詞 >< 介詞短語

47、>a_girl_<動(dòng)詞 >< 名詞短語 >< 介詞短語>a_girl_touches_< 名詞短語 >< 介詞短語 >a_girl_touches_< 冠詞 >< 名詞 >< 介詞短語 >a_girl_touches_the_< 名詞 >< 介詞短語 >a_girl_touches_the_boy_<介詞短語 >a_girl_touches_the_boy_<介詞 >< 復(fù)合名詞 >a_girl_touches_the_boy_wit

48、h_<復(fù)合名詞 >a_girl_touches_the_boy_with_<冠詞 >< 名詞 >a_girl_touches_the_boy_with_the_< 名詞 >a_girl_touches_the_boy_with_the_flower含義是：女孩用花碰這個(gè)男孩2.10 給出產(chǎn)生語言A=a ibjck| i,j,k0且或者i=j或者j=k的上下文無關(guān)文法。你給出的文法是歧義的嗎?為什么？解：下面是產(chǎn)生 A的一個(gè)CFG:UV|AB aUb| cV| aA|B bUc| 這個(gè)CFG是歧義的，因?yàn)樽址?abc有如下兩種不同的最左派生：S

49、UV aUbV abV abcV abcS AB aAV aV abVc abc2.11 給出識(shí)別2.10中語言A的下推自動(dòng)機(jī)的非形式描述。解：其非形式描述為：此PDA有兩個(gè)非確定性的分支：一個(gè)分支先讀a,并且每讀一個(gè) a將一個(gè)a推入棧中，當(dāng)碰到 b時(shí)，每讀一個(gè)b從棧中彈出一個(gè)a,若沒有a可彈出則拒絕，最后讀 c且不改變棧中的內(nèi)容，若此時(shí)棧為空則接受。另一個(gè)分支也是先讀 a,但不改變棧中內(nèi)容，當(dāng)碰到b時(shí)，每讀一個(gè)b將一個(gè)b推入棧中，再讀c,每 讀一個(gè)c從棧中彈出一個(gè)b,若沒有a可彈出則拒絕，若 c讀完后棧為空則接受。開始時(shí)，讀輸入串的字 符，非確定性的選擇一個(gè)分支運(yùn)行，若有一個(gè)分支接受則接受，

50、否則拒絕。2.14 設(shè)有上下文無關(guān)文法 G:S TT|UU 0U00|#T 0T|T0|#a.用普通的語言描述 L(G)。b.證明L(G)不是正則的。解：a. A=0#0j#0k |i,j, k 0 0i#02i|i 0。b.取 s=0p#02p,則對(duì)于任意劃分 s=xyz(|xy| p, |y|>0), xy nz=0 p+i #0 2p A,所以不是正則的。2.15 用定理2.6中給出的過程，把下述CFG轉(zhuǎn)換成等價(jià)的喬姆斯基范式文法。A BAB|B|B 00|解：添加新起始變?cè)?So,So AA BAB|B|B 00|去掉A ,So AA BAB|AB|BA|B|BBB 00去掉So

51、 A,So BAB|AB|BA|00|BBA BAB|AB|BA|00|BBB 00去掉BSo AA BAB|AB|BA|B|B 00去掉A BSo AA BAB|AB|BA|00|BBB 00添加新變?cè)猄o VB|AB|BA|UU|BBA VB|AB|BA|UU|BBB UUV BA給出每一個(gè)2.x先說明如何把正則表達(dá)式直接轉(zhuǎn)換成等價(jià)得上下文無關(guān)文法，然后利用問題xxx的結(jié)果,正則語言都是上下文無關(guān)文法的一個(gè)證明。解：設(shè)有正則表達(dá)式 T,將其轉(zhuǎn)化為上下文無關(guān)文法。1）首先添加S 且令S為起始變?cè)?）根據(jù)T的不同形式，按如下方式添加規(guī)則則在規(guī)則集中添加則在規(guī)則集中添加則在規(guī)則集中添加則在規(guī)則

52、集中添加則在規(guī)則集中添加T則在規(guī)則集中添加 . 若T = a .若T=, .若T=, .若T=A B .若丁=人8, .若T=A*,T a,T ,TT A|B,AB,T A,和 A AA|3)若有新添加的變?cè)?，則根據(jù)其所對(duì)應(yīng)的表達(dá)式轉(zhuǎn)第2步，直到?jīng)]有新的變?cè)霈F(xiàn)。下面來證明每一個(gè)正則語言都是上下文無關(guān)的由正則語言與正則表達(dá)式的等價(jià)性可知：對(duì)于一個(gè)正則語言都存在一個(gè)描述他的正則表達(dá)式，由前述討論可知，這個(gè)正則表達(dá)式可轉(zhuǎn)換為一個(gè)與之等價(jià)的上下文無關(guān)的文法。因此，此正則語言能由這個(gè)上下文無關(guān)文法產(chǎn)生。所以正則語言是上下文無關(guān)的。2.18 a.設(shè)C是上下文無關(guān)語言，R是正則語言。證明語言C R是上下文無關(guān)的。b.利用a證明語言A=w | wa,b,c *,且含有數(shù)目相同的 a,b,c證明：a.設(shè) P=(Qi, , , i,qi,Fi)是一個(gè)識(shí)別 C 的 PDA , N=(Q 2, , 2,q2,F2)是識(shí)別 R 的一臺(tái) NFA。下面構(gòu)造識(shí)別C R的PDA如下S=(Q, , ,q0,F):1) Q=Q 1XQ2,是狀態(tài)集，2) q