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

1、計算理論習(xí)題解答練習(xí)1.1 圖給出兩臺DFA M1和M2的狀態(tài)圖. 回答下述有關(guān)問題.a. M1的起始狀態(tài)是q1b. M1的接受狀態(tài)集是q2c. M2的起始狀態(tài)是q1d. M2的接受狀態(tài)集是q1，q4e. 對輸入aabb,M1經(jīng)過的狀態(tài)序列是q1，q2，q3，q1，q1f. M1接受字符串a(chǎn)abb嗎？否g. M2接受字符串嗎？是1.2 給出練習(xí)2.1中畫出的機器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是起始狀態(tài)5） F1=q2M2=(Q2,2,q2

2、,F2) 其中1） Q2=q1,q2,q3,q4;2） =a,b;3）2為：a b q1 q2 q3 q4 q1 q2 q3 q4 q2 q1q3 q43） q2是起始狀態(tài)4） F2=q1,q41.3 DFA M的形式描述為 ( q1，q2，q3，q4，q5，u,d,q3，q3),其中在表2-3中給出。試畫出此機器的狀態(tài)圖。q1q5q4q2q3uduuuudddd1.6 畫出識別下述語言的DFA的狀態(tài)圖。a)w | w從1開始以0結(jié)束001110,100100110,1b)w | w至少有3個10,110011010c) w | w含有子串01010,100,10,1110,10d) w |

3、w的長度不小于3，且第三個符號為00,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含有偶數(shù)個0，或恰好兩個1m) 空集 n) 除空串外的所有字符串0,10,10,11.

4、7 給出識別下述語言的NFA，且要求符合規(guī)定的狀態(tài)數(shù)。000,1a. w | w以00結(jié)束，三個狀態(tài)010,1010,1b. 語言w | w含有子串0101，即對某個x和y，w=x0101y，5個狀態(tài).e011101000ec. 語言w | w含有偶數(shù)個0或恰好兩個1，6個狀態(tài)。d. 語言0，2個狀態(tài)。0e. 語言0*1*0*0，3個狀態(tài)。e0010f. 語言，1個狀態(tài)。g. 語言0*，1個狀態(tài)。02.11證明每一臺NFA都能夠轉(zhuǎn)換成等價的只有一個接受狀態(tài)的NFA。證明:設(shè)NFA M=Q，,q0,F，F(xiàn)=ri1，rik.添加一個狀態(tài)p后，ri1，rik分別向p引箭頭，將ri1，rik變?yōu)榉墙邮?/p>

5、狀態(tài)，p變?yōu)榻邮軤顟B(tài)。又因為添加箭頭不影響NFA識別語言，所以命題成立。2.14 a 證明：設(shè)M是一臺語言B的DFA，交換M的接狀態(tài)與非接受狀態(tài)得到一臺新的DFA，則這臺新的DFA是識別B 的補集，因此，正則語言類受在補運算下封閉。b 舉例說明：設(shè)M是一臺識別語言B的NFA，交換M的接受狀態(tài)與非接受狀態(tài)得到一臺新的NFA，這臺新的NFA不一定識別B的補集。NFA識別的語言類在補集下封閉嗎？解釋你的回答。解：a. M是DFA, M是Q,q0,F,令N=Q,q0,Q-F,設(shè)=12n是字母表上任意字符串，因為M與N均為DFA,所以必然存在Q中狀態(tài)序列r0,r1,rn,使得：r0=q0, (ri, i

6、+1)=ri+1, i=0,n-11)若rnÎF 則ÎB;2)若rnÏF,則rnÎQ-F,即N接受，若ÏB,所以N接受B的補集，即B的補集正則。所以，正則語言類在補運算下封閉。0b. 設(shè)B為0。NFA M：0可識別它。依題對它作變換，得到N：則N識別的語言不是B的子集。所以交換M的接受狀態(tài)與非接受狀態(tài)得到的新的NFA不一定識別B的補集。但是由于NFA識別的語言類與DFA識別的語言類相同，即正則語言類。由a的證明，正則語言類在補運算封閉，可知，NFA識別的語言類-正則語言類在補運算下封閉。若NFA識別語言A，必有 等價的DFA識別A,從而由a知，

7、可交換DFA的接受與非接受狀態(tài)構(gòu)造識別A的補集的DFA,則必有等價的NFA識別A的補集。只是，該NFA未必有原NFA交換接受與非接受狀態(tài)構(gòu)造而成。1.15 給出一個反例，說明下述構(gòu)造不能證明定理2.24，即正則語言類在星號運算下封閉。設(shè)N=（Q1,1,q1,F1）識別A1。如下構(gòu)造N=（Q1,1,q1,F1）。N應(yīng)該識別A1*。a. N的狀態(tài)集是N1的狀態(tài)集。b. N的起始狀態(tài)是N1的起始狀態(tài)相同。c. F=q1F1。F的接受狀態(tài)是原來的接受狀態(tài)加上它的起始狀態(tài)。d. 定義如下：對每一個q屬于Q和每一個a屬于。解：設(shè)N1識別語言A=至少含有一個1，其中輸入字母表為0，1，可知A*=空串或至少含

8、有一個1。10,10,1ea,bab12N1: N:按上述規(guī)定構(gòu)造N的狀態(tài)圖如上。可以看出L(N)=0,1*不等于A*. 所以如此構(gòu)造的N不一定識別A*.aa,beba1231.16 使用定理2.19中給出的構(gòu)造，把下圖中的兩臺非確定型有窮自動機轉(zhuǎn)換成等價的確定型有窮自動機。10,10,1 a)， b)，解：a), b)aab123b123Æaba,ba,bab12b12Æaa,b2.13 給出生成練習(xí)2.4中語言的正則表達式。(注: 答案不唯一)a. w | w從1開始以0結(jié)束 1*0.b. w | w至少有3個1 *1*1*1*.c. w | w含有子串0101 *01

9、01*.d. w | w的長度不小于3，且第三個符號為0 0*.e. w | w從0開始且為奇長度，或從1開始且為偶長度 0()*È1()*.f. w | w不含子串110 (0È10) *1*.g. w | w的長度不超過5 eÈÈÈÈÈ.h. w | w是除11和111以外的任何字符 0*È10*È110*È111*.i. w | w的奇位置均為1 (1)*( eÈ1).j. w | w至少含有2個0，且至多含有1個1 0*(00È010È001È10

10、0) 0*.k. ,0. È0.l. w | w含有偶數(shù)個0，或恰好兩個1 (1*01*0)*1*È0*10*10*.m. 空集. Æ.n. 除空串外的所有字符串*.1.19對下述每一個語言，給出4個字符串，2個是這個語言的成員，2個不是這個語言的成員。這里假設(shè)字母表=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

11、 非成員：aa，abbf. abaÈbab 成員：aba，bab 非成員：a，bg. (eÈa)b 成員：b，ab 非成員：a，bbh. (aÈbaÈbb) * 成員：a，bb 非成員：e，b1.21 使用引理2.32中敘述的過程，把圖2-38中的有窮自動機轉(zhuǎn)換成正則表達式。bba,baa123bab12aa), b),解: a) a*b(aÈba*b)*b) eÈ(aÈb)a*b(aaÈabÈb)a*b*(aÈe).(注：答案不唯一)1.29利用泵引理證明下述語言不是正則的。a. A1=0n1

12、n2n | n³0。證明：假設(shè)A1是正則的。設(shè)p是泵引理給出的關(guān)于A1的泵長度。令S=0p1p2p,S是A1的一個成員且S的長度大于p，所以泵引理保證S可被分成3段S=xyz且滿足泵引理的3個條件。根據(jù)條件3，y中只含0，xyyz中，0比1、2多，xyyz不是A1的成員。違反泵引理的條件1，矛盾。A1不是正則的。b. A2=www | wÎa,b*.證明：假設(shè)A2是正則的。設(shè)p是泵引理給出的關(guān)于A2的泵長度。令S=apbapbapb,S是A2的一個成員且S的長度大于p，所以泵引理保證S可被分成3段S=xyz且滿足泵引理的3個條件。根據(jù)條件3，y中只含a，所以xyyz中第一個

13、a的個數(shù)將比后兩個a的個數(shù)多，故xyyz不是A2的成員。違反泵引理的條件1，矛盾。A2不是正則的。c. A3=a2n | n³0.(在這里，a2n表示一串2n個a .)證明：假設(shè)A3是正則的。設(shè)p是泵引理給出的關(guān)于A3的泵長度。令S= a2p，S是A2的一個成員且S的長度大于p，所以泵引理保證S可被分成3段S=xyz且滿足泵引理的3個條件。即對任意的i³0，xyiz都應(yīng)在A3中，且xyiz與xyi+1z的長度都應(yīng)是2的冪. 而且xyi+1z的長度應(yīng)是xyiz的長度的2n倍(n³1)。于是可以選擇足夠大的i，使得|xyiz|=2n>p. 但是|xyi+1z|-

14、|xyiz|=|y|£p. 即|xyi+1z|<2n+1, 矛盾。A3不是正則的。1.30下面“證明”0*1*不是正則語言，指出這個“證明”中的錯誤。(因為0*1*是正則的，所以一定錯誤。) 采用反證法證明。假設(shè)0*1*是正則的。令P是泵引定理給出的關(guān)于0*1*的泵長度。取S為字符串0p1p。S是0*1*的一個成員，但是例2.38已證明S不能被抽取。于是得到矛盾，所以0*1*不是正則的。解：在例2.38中的語言是0n1n | n³0，取S為字符串0p1p，S確實不能被抽?。坏槍φZ言0*1*，S是能被抽取的。將S分成三段S=xyz，由泵引理的條件3，y僅包含0，而xy

15、iz屬于語言0*1*，即S能被抽取，故題設(shè)中的“證明”不正確。b/1a/0q3q2q1b/0a/1b/1a/11.24有窮狀態(tài)轉(zhuǎn)換器(FST)是確定性有窮自動機的一種類型。它的輸出是一個字符串，而不僅僅是接受或拒絕。圖239是兩臺有窮狀態(tài)狀態(tài)轉(zhuǎn)換器T1和T2的狀態(tài)圖。2/10/01/00/0q1q21/12/1T1 T2FST的每一個轉(zhuǎn)移用兩個符號標(biāo)記，一個指明該轉(zhuǎn)移的輸入符號，另一個指明輸出符號。兩個符號之間用斜杠“/”把它們分開。在T1中，從q1到q2的轉(zhuǎn)移有輸入符號2和輸出符號1。某些轉(zhuǎn)移可能有多對輸入-輸出，比如T1中從q1到它自身的轉(zhuǎn)移。FST在對輸入串w計算時，從起始狀態(tài)開始，一個

16、接一個地取輸入符號w1¼wn，并且比照輸入標(biāo)記和符號序列w1¼wn=w進行轉(zhuǎn)移。每一次沿一個轉(zhuǎn)移走一步，輸出對應(yīng)的輸出符號。例如，對輸入2212011，機器T1依次進入狀態(tài)q1, q2, q2, q2, q2, q1, q1, q1和輸出1111000。對輸入abbb，T2輸出1001。給出在下述每一小題中機器進入的狀態(tài)序列和產(chǎn)生的輸出。a. T1對輸入串011, 輸出：000, 狀態(tài)序列：q1, q1, q1, q1.b. T1對輸入串211, 輸出：111, 狀態(tài)序列：q1, q2, q2, q2.c. T1對輸入串0202, 輸出：0101, 狀態(tài)序列：q1, q1,

17、 q2, q1, q2。d. T2對輸入串b, 輸出：1, 狀態(tài)序列：q1, q3.e. T2對輸入串bbab, 輸出：1111, 狀態(tài)序列：q1, q3, q2, q3, q2.f. T2對輸入串bbbbbb, 輸出：110110, 狀態(tài)序列：q1, q3, q2, q1, q3, q2, q1。g. T2對輸入串e, 輸出：e, 狀態(tài)序列：q1。1.25 給出有窮狀態(tài)轉(zhuǎn)換器的形式定義。解：有窮狀態(tài)轉(zhuǎn)換器FST是一個五元組(Q,q0)1) Q是一個由窮集合，叫做狀態(tài)集2) 是一個由窮集合，叫做輸入字母表3) 是一個由窮集合，叫做輸出字母表4) ：Q×àQ×是轉(zhuǎn)移

18、函數(shù)5) q0是起始狀態(tài)FST計算的形式定義：M=(Q,q0)是一臺由窮狀態(tài)轉(zhuǎn)換器，w=w1w2¼wn是輸入字母表上的一個字符串。若存在Q中的狀態(tài)序列：r0, r1, ¼rn和輸出字母表上的一個字符串s=s1sn, 滿足下述條件：1） r0=q0;2） (ri,wi+1)=(ri+1, si+1), i=0,1,¼,n-1則M在W的輸入下輸出s.1.26利用你給練習(xí)2.20的答案，給出練習(xí)2.19中畫出的機器T1和T2的形式描述。解：有窮狀態(tài)轉(zhuǎn)換器T1的形式描述為：T1=(q1, q2 , 0，1，2, q1, 0,1)其中轉(zhuǎn)移函數(shù)為：012q1q1/0q1/0q

19、2/1q2q1/0q2/1q2/1有窮狀態(tài)轉(zhuǎn)換器T2的形式描述為：T2=(q1, q2, q3, a, b, q1, 0,1)其中轉(zhuǎn)移函數(shù)為：abq1q2/1q3/1q2q3/1q1/0q3q1/0q2/11.27 給出一臺具有下述行為的FST的狀態(tài)圖。它的輸入、輸出字母表都是0,1。它輸出的字符串與輸入的字符串偶數(shù)為相同、奇數(shù)位相反。例如，對于輸入0000111，它應(yīng)該輸出1010010。1/00/11/10/0q1q2解：1.46 證明：a) 假設(shè)0n1m0n|m,n0是正則的，p是由泵引理給出的泵長度。取s0p1q0p，q>0。由泵引理條件3知，|xy|p，故y一定由0組成，從而字

20、符串xyyz中1前后0的數(shù)目不同，即xyyz不屬于該語言，這與泵引理矛盾。所以該語言不是正則的。b) 假設(shè)0n1n|n0的補集是正則的，則根據(jù)正則語言在補運算下封閉可得0n1n|n0是正則的，這與已知矛盾，故假設(shè)不成立。所以該語言不是正則的。記c=0m1n|mn，c為c的補集，c0*1*=0n1n|n0，已知0n1n|n0不是正則的。若 c是正則的，由于0*1*是正則的，那么c0*1*也應(yīng)為正則的。這與已知矛盾，所以 c不是正則的。由正則語言在補運算下的封閉性可知c也不是正則的。c) w | wÎ0,1*不是一個回文的補集是w | wÎ0,1*是一個回文，設(shè)其是正則的，令p

21、是由泵引理給出的泵長度。取字符串s=0p1q0p，顯然s是一個回文且長度大于p。由泵引理條件3知|xy|p，故y只能由0組成。而xyyz不再是一個回文，這與泵引理矛盾。所以w | wÎ0,1*是一個回文不是正則的。由正則語言在補運算下的封閉性可知w | wÎ0,1*不是一個回文也不是正則的。1.31 對于任意的字符串w=w1w2wn，w的反轉(zhuǎn)是按相反的順序排列w得到的字符串，記作wR，即wR=wnw2w1。對于任意的語言A，記 AR=wR | ÎA證明：如果A是正則的，則AR也是正則的。證明： 因為A是正則語言，所以可以用NFA來表示該語言，現(xiàn)在來構(gòu)造AR的NFA

22、，將NFA A中的接受態(tài)變?yōu)橹虚g態(tài)，起始態(tài)變?yōu)榻邮軕B(tài)，再添加一新的起始態(tài)，并用箭頭連接至原來的接受態(tài)，其它所有的箭頭反向。 經(jīng)過變換后得到NFA變成描述AR的NFA.000001,010,111S3=1.32 令å3包括所有高度為3的0和1的列向量。å3上的字符串給出三行0和1的字符串。把每一行看作一個二進制數(shù)，令B= wÎå3* | w最下面一行等于上面兩行的和例如，, 而ÎBÏB001100110001101證明B是正則的。證明：由題設(shè)B的定義可知，w上面兩行之和減去下面一行結(jié)果為零，由此可設(shè)計NFA M (Q, , , q0,

23、F)，其中å=å3。Q=q0,q1。q0狀態(tài)表示上一次運算的進位為0，q1狀態(tài)表示上一次運算的進位為1。由下表給出：000001010011100101110111q0q0ÆÆq0Æq0q1Æq1Æq0q1Æq1ÆÆq1F=q0q0q1001110101101000111100010,狀態(tài)圖為：所以可知自動機M識別的是語言BR，因此BR是正則的。由題2-24的結(jié)論可知B也是正則的。,S2=000111101.33 令S2包含所有高度為2的0和1的列。S2上的字符串給出兩行0和1的字符串。把每一行

24、看作一個二進制數(shù)，令C= wÎå2* | w下面一行等于上面一行的3倍 。證明C是正則的?？梢约僭O(shè)已知問題2.24中的結(jié)果。q0q1q2001111000110證明：如下的NFA識別CR：其中q0狀態(tài)表示上一次運算的進位為0，q1狀態(tài)表示上一次運算的進位為1, q2狀態(tài)表示上一次運算的進位為2。q0q1q2001101101100如下的NFA識別C：其中狀態(tài)q0,q1,q2分別表示目前讀到的下面的數(shù)減上面的數(shù)的3倍余0,1,2的情況。,S2=000111101.34令S2包含所有高度為2的0和1的列。S2上的字符串給出兩行0和1的字符串。把每一行看作一個二進制數(shù)，令D= w

25、Îå2* | w上一行大于下一行 。證明D是正則的。證明：由題設(shè)可設(shè)計自動機M=(Q, , , q, F)，其中Q=q1,q2，F(xiàn)=q2,轉(zhuǎn)移函數(shù)與狀態(tài)圖為：00011011q1q1Æq2q1q2q2q2q2q2q1q200110110110010,1.35設(shè)2與問題2.26中的相同。把每一行看作0和1的字符串，令E=wÎå2* | w的下一行是上一行的反轉(zhuǎn)，證明E不是正則的。10p01p證明：假設(shè)E是正則的，令p是有泵引理給出的泵長度。10選擇字符串s= 。于是s能夠被劃分為xyz且滿足泵引理的條件。根據(jù)條件3，y僅能取包含 的部分，當(dāng)添加一

26、個y時，xyyz不屬于E. 所以E不是正則的.1.36 令Bn=ak | k是n的整數(shù)倍。證明對于每一個n³1, Bn是正則的。證明：設(shè)字母表為a，則an是一正則表達式。所以，(an)*也是正則表達式。由題意Bn=(an)*,即Bn可以用正則表達式表示。所以，Bn也是正則的。1.37 令Cn=x | x是一個二進制數(shù)，且是n的整數(shù)倍。證明對于每一個n³1, Cn是正則的。證明：下面的DFA識別Cn：(正向讀)M=( Q, 0,1 , d , q0 , F ), 其中Q0,1,2,，n-1,d( i,1)=2i+1 mod n, d( i,0 )=( 2i mod n), i

27、=0,1,2,，n-1,起始狀態(tài)為0, F0.這里i表示當(dāng)前數(shù)mod n余i.下面的DFA識別CnR：(反向讀)M=( Q, 0,1 , d , q0 , F ), 其中Q(i,j)|i,j=0,1,2,，n-1,d(i,j),1)=( 2i mod n, (2i+j)mod n ), d(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(例如，若讀下一位將達到k位，則下一位所表示單位數(shù)為10k-1).1.38 考慮一種叫做

28、全路徑NFA的新型有窮自動機。一臺全路徑NFA M是5元組 ( Q, å, d, q0, F). 如果M對xÎå*的每一個可能的計算都結(jié)束在F中的狀態(tài)，則M接受x。注意，相反的，普通的NFA只需有一個計算結(jié)束在接受狀態(tài)，就接受這個字符串。證明：全路徑NFA識別正則語言。證明：一個DFA一定是一個全路徑NFA。所以下面只需證明，任意全路徑NFA，都有一個與之等價的DFA。設(shè)有一全路徑NFA N=( Q, , , q0, F)，構(gòu)造一個新與N等價的全路徑NFA N1( Q1, , 1, q0, F), 其中Q1=QÈs, sÏQ。對于任意q

29、6;Q1, aÎ (q,a)， q ¹ s, 且(q,a) ¹Æ1(q,a) = s, q ¹ s, 且(q,a) =Æ s, q=s.現(xiàn)在來構(gòu)造一個與全路徑NFA N1等價的DFA M(Q2, , 2, q1, F2). 其中1) Q2=Power(Q1), 即Q1的所有子集組成的集合(也即Q1的冪集)；2) 定義函數(shù)E: Q2àQ2為：對任意RÎQ2, ；3) q1=E(q0);4) 對于任意的R屬于Q2, a屬于, .5) F2= RÎQ2 | RÍF。綜上所述，DFA等價于全路徑NFA。

30、1.40如果存在字符串z使得xz=y,則稱字符串x是字符串y的前綴。如果x是y的前綴且xy,則稱x是y的真前綴。下面每小題定義一個語言A上的運算。證明：正則語言類在每個運算下封閉。 a) NOPREFIX(A)=A|的任意真前綴都不是A的元素 b)NOEXTEND(A)= A|不是A中任何字符串的真前綴證明：假設(shè)DFA M=( Q, , , q0, F)識別語言A。a) 構(gòu)造NFA N1=( Q, , 1, q0, F)識別語言NOPREFIX(A)。其中， 對任意qÎF, a Îe, 所以，即NOPREFIX(A)為正則語言，亦即正則語言類A在NOPREFIX(A)運算下

31、封閉。b) 構(gòu)造NFA N2=( Q, , , q0, F2)識別語言NOEXTEND(A)。F2構(gòu)造如下：對M中的任一接受狀態(tài)qi, 若存在一條從它出發(fā)到達某接受狀態(tài)(含本身)的路徑，則將狀態(tài)qi改為非接受狀態(tài); 最后剩下的接受狀態(tài)集記為F2. 所得的NFA N2即識別NOEXTEND(A)。所以，NOEXTEND(A)為正則語言，亦即正則語言類A在運算NOEXTEND(A)下封閉。01011011001100011.48 證明：構(gòu)造NFA N如下：由于該NFA識別D，故D是正則語言。1.50參見練習(xí)1.24中給出的有窮狀態(tài)轉(zhuǎn)換器的非形式定義。證明不存在FST對每一個輸入w能夠輸出wR，其中

32、輸入和輸出的字母表為0,1。證明：假設(shè)存在一臺FST對每個輸入w能夠輸出wR。則對于輸入串w1=100, w2=101. 該FST可分別輸出w1R=001，w2R=101，于是對于它的起始狀態(tài)和輸入字符1，會輸出1和0兩個不同字符，這與FST是確定性有窮自動機相矛盾。所以，不存在一臺FST對每個輸入w能夠輸出wR。1.51證明: 1) 自反性。即對任意字符串x，xºLx。這是因為對于每個字符串z均有xz和xz同時是或不是L的成員。2) 對稱性。即對任意字符串x和y, 若xºLy，則yºLx。這是因為若xºLy，則對于每個字符串z, xz和yz同時是或不是

33、L的成員，那么yz和xz同時是或不是L的成員, 于是yºLx。3) 傳遞性。即對任意字符串x,y和z, 若xºLy且yºLz，則xºLz。這是因為對任意字符串u, 由xºLy知xu和yu同時是或不是L的成員, 由yºLz知yu和zu同時是或不是L的成員, 所以xu和zu同時是或不是L的成員, 此即xºLz。綜上所述，ºL是自反的，對稱的，傳遞的，所以是一個等價的關(guān)系。1.53 令=0，1，+，=和ADD= x=y+z | x,y,z是二進制整數(shù)，且x是y與z的和證明ADD不是正則的。證明：假設(shè)ADD是正則的。設(shè)P是

34、泵引理給出的關(guān)于ADD的泵長度。令s為1P=10P-1+1P-1。于是s能夠被劃分成xyz，且滿足泵引理的條件。根據(jù)條件3，y=1i, i>0. 所以xyyz為1P+i=10P-1+1P-1ÏADD。故ADD不是正則的。1.54證明：語言F=aibjck | i,j,k³0且若i=1，則j=k滿足泵引理的3個條件，雖然它不是正則的。解釋這個事實為什么與泵引理不矛盾。證明：對任意正數(shù)p>1，設(shè)S是F中的一個成員且S的長度不小于p。將S分成3段S=xyz。(1) i=0，j=0. 此時S=ck (k>0)。取x=e, y=c, z=ck-1. 則對任意i

35、79;0, xyizÎF。(2) i=0，j>0. 此時S=bjck(j>0, k³0).取x=e, y=b, z=bj-1ck. 則對任意i³0, xyizÎF。(3) i=1. 此時S=abjck(j³0, k³0).取x=e, y=a, z=bjck. 則對任意i³0, xyizÎF。(4) i=2. 此時S= a2bjck(j³0, k³0).取x=e, y=a2, z=bjck. 則對任意i³0, xyizÎF。(5) i>2. 此時S= aibj

36、ck(i³3, j³0, k³0). 取x=e, y=a, z=ai-1bjck. 則對任意i³0, xyizÎF。綜上所述，語言F滿足泵引理的3個條件。這一事實不與泵引理矛盾是因為泵引理是正則語言的必要不充分條件。1.55 求最小泵長度。 a. 0001*的最小泵長度為4.因為對任何s 若|s|=3則s只含有0，不能被抽取。若|s|4時，把s劃分為x=000 y=1 z為其余部分，則xyizÎ0001*。 b. 0*1*最小泵長度為1.若|s|1時,S分兩種情況：1 S以0開頭,令x=e, y=0, z為其余則xyizÎ0

37、*1*.2 S以1開頭,令x=e, y=1, z為其余則xyizÎ0*1*.c. (01)*最小泵長度為2. 若|s|2時,令x=e, y=01, z為其余, 則xyizÎ(01)*.d. 01，其最小泵長度為3。因為語言中只有有限個字符串時，任何一個字符串都不能被抽取。所以有限語言的泵長度為其最長字符串的長度加1。此時沒有比泵長度長的字符串，前提假所以命題真。e. e，其最小泵長度為1.理由類似于d中所述。2.39 證明：設(shè)對于每一個k>1，Ak= w | w包含子串1k-1Í1*，下面證明Ak能被一臺k個狀態(tài)的DFA識別，而不能被只有k1個狀態(tài)的DFA識

38、別。顯然，Ak能被k個狀態(tài)的DFA M=(q1,q2,qk, 1, d, q1, qk).識別, 其中d(qi,1)=qi+1(i=1,2,k-1), d(qk,1)=qk。假設(shè)AK可以被只有k-1個狀態(tài)的DFAM1識別?？紤]這樣一個輸入串s=1k-1，設(shè)M識別s的狀態(tài)序列是r1, r2,rk,由于M的狀態(tài)只有k-1個，根據(jù)鴿巢原理，r1,r2,rk中必有兩個重復(fù)的狀態(tài)，假設(shè)是ri=rj (0£i<j£k)，此時可知，字符串x=1j-i把M從ri帶到了rj。由于ri,rj是同一個狀態(tài)，所以去掉s中的x子串，M仍可識別s的剩余部分，即M識別1k-1-(j-i)，這與M1

39、識別Ak相矛盾。故Ak不能被只有k-1個狀態(tài)的DFA M識別。所以，對于每一個k>1，存在AK，使得AK能被K個狀態(tài)的DFA識別，而不能被只有k-1個狀態(tài)的DFA識別。2.1 略。2.2 a. 利用語言A=ambncn | m,n³0和A=anbncm | m,n³0以及例3.20，證明上下文無關(guān)語言在交的運算下不封閉。b. 利用(a)和DeMorgan律(定理1.10)，證明上下文無關(guān)語言在補運算下不封閉。證明：a.先說明A,B均為上下文無關(guān)文法，對A構(gòu)造CFG C1S®aS|T|eT®bTc|e對B,構(gòu)造CFG C2S®Sc|R|eR

40、®aRb由此知 A,B均為上下文無關(guān)語言。但是由例3.20, AB=anbncn|n³0不是上下文無關(guān)語言，所以上下文無關(guān)語言在交的運算下不封閉。b.用反證法。假設(shè)CFL在補運算下封閉，則對于(a)中上下文無關(guān)語言A,B，,也為CFL，且CFL對并運算封閉，所以也為CFL，進而知道為CFL，由DeMorgan定律AB，由此AB是CFL,這與(a)的結(jié)論矛盾，所以CFL對補運算不封閉。2.3 略。2.4和2.5 給出產(chǎn)生下述語言的上下文無關(guān)文法和PDA，其中字母表S=0,1。e,1®e 1, e®10, e®ee,1®e e,1

41、4;e a. w | w至少含有3個1SA1A1A1AA0A|1A|eb. w | w以相同的符號開始和結(jié)束1,e®11,e®e0,e®e0,e®01,1®e0,0®eS0A0|1A1A0A|1A|e1,e®e0,e®e1,e®e0,e®ec. w | w的長度為奇數(shù)S0A|1AA0B|1B|eB0A|1Ad. w | w的長度為奇數(shù)且正中間的符號為0S0S0|1S1|0S1|1S0|01,e®00,e®e0,e®01,0®e0,0®ee,e&#

42、174;$e,$®e1,e®1e,1®e0,e®0e,1®ee,e®$e,$®e1,0®e0,1®ee. w | w中1比0多SA1AA0A1|1A0|1A|AA|ef. w | w=wRS0S0|1S1|1|01,e®10,e®e0,e®01,1®e0,0®ee,e®$e,$®e1,e®ee,e®eg. 空集SS2.6 給出產(chǎn)生下述語言的上下文無關(guān)文法：a 字母表a,b上a的個數(shù)是b的個數(shù)的兩倍的所有字符串組成的集

43、合。 SbSaSaS|aSbSaS|aSaSbS|eb語言anbn|n³0的補集。見問題3.25中的CFG:SaSb|bY|TaTaT|bT|ecw#x | w, xÎ0,1*且wR是x的子串。SUVU0U0|1U1|WWW1|W0|#V0V|1V|edx1#x2#¼#xk|k³1, 每一個xiÎa,b* , 且存在i和j使得xixjR。SUVWUA|eAaA|bA|#A|#VaVa|bVb|#B|#BaB|bB|#B|#WB|e2.8 證明上下文無關(guān)語言類在并,連接和星號三種正則運算下封閉。a. AÈB方法一：CFG。設(shè)有CFG G

44、1(Q1,S,R1,S1)和G2=(Q2,S,R2,S2)且L(G1)=A, L(G2)=B。構(gòu)造CFG G=(Q,S,R,S0)，其中Q= Q1ÈQ2ÈS0, S0是起始變元，R= R1ÈR2ÈS0® S1|S2.方法二：PDA。設(shè)P1=(Q1,S,G1,d1,q1,F1)識別A，P2=(Q1,S,G2,d2,q2,F2)是識別B。則如下構(gòu)造的P=(Q,S,G,d,q0,F)識別AÈB，其中1) Q=Q1ÈQ2Èq0是狀態(tài)集，2) GG1ÈG2，是棧字母表，3) q0是起始狀態(tài)，4) FF1È

45、F2是接受狀態(tài)集，5) d是轉(zhuǎn)移函數(shù)，滿足對任意qÎQ, aÎSe,bÎGed(q,a,b)=b. 連接AB方法一：CFG。設(shè)有CFG G1(Q1,S,R1,S1)和G2=(Q2,S,R2,S2)且L(G1)=A, L(G2)=B。構(gòu)造CFG G=(Q,S,R,S0)，其中Q= Q1ÈQ2ÈS0, S0是起始變元，R= R1ÈR2ÈS0® S1S2.方法二：PDA。設(shè)P1=(Q1,S,G1,d1,q1,F1)識別A，P2=(Q1,S,G2,d2,q2,F2)是識別B，而且P1滿足在接受之前排空棧(即若進入接受狀態(tài)，

46、則棧中為空)這個要求。則如下構(gòu)造的P=(Q,S,G,d,q1,F)識別AÈB，其中1) Q=Q1ÈQ2是狀態(tài)集，2) GG1ÈG2，是棧字母表，3) q1是起始狀態(tài)，4) FF1ÈF2是接受狀態(tài)集，5) d是轉(zhuǎn)移函數(shù)，滿足對任意qÎQ, aÎSe,bÎGed(q,a,b)=c. A*方法一：CFG。設(shè)有CFG G1(Q1,S,R1,S1)，L(G1)=A。構(gòu)造CFG G=(Q,S,R,S0)，其中Q= Q1 ÈS0, S0是起始變元，R= R1ÈS0®S0S0|S1|e.方法二：PDA。設(shè)P1=

47、(Q1,S,G1,d1,q1,F1)識別A，而且P1滿足在接受之前排空棧(即若進入接受狀態(tài)，則棧中為空)這個要求。則如下構(gòu)造的P=(Q,S,G,d,q1,F)識別A*，其中1) Q=Q1Èq0是狀態(tài)集，2) GG1，是棧字母表，3) q0是起始狀態(tài)，4) FF1Èq0是接受狀態(tài)集，5) d是轉(zhuǎn)移函數(shù)，滿足對任意qÎQ, aÎSe,bÎGed(q,a,b)=2.9 證明在3.1節(jié)開始部分給出的文法G2中，字符串the girl touches the boy with the flower有兩個不同的最左派生，敘述這句話的兩個不同意思。<句

48、子>Þ<名詞短語><動詞短語>Þ<復(fù)合名詞><動詞短語>Þ<冠詞><名詞><動詞短語>Þa_<名詞><動詞短語>Þa_girl_<動詞短語>Þa_girl_<復(fù)合名詞>Þa_girl_<動詞>< 名詞短語>Þa_girl_touches_< 名詞短語>Þ a_girl_touches_<復(fù)合名詞><

49、;介詞短語>Þ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_boy_with_<冠詞><名詞>

50、;Þa_girl_touches_the_boy_with_the_<名詞>Þa_girl_touches_the_boy_with_the_flower含義是 ：女孩碰這個帶著花的男孩<句子>Þ<名詞短語><動詞短語>Þ<復(fù)合名詞><動詞短語>Þ<冠詞><名詞><動詞短語>Þa_<名詞><動詞短語>Þa_girl_<動詞短語>Þa_girl_<復(fù)合動詞><

51、;介詞短語>Þa_girl_<動詞>< 名詞短語><介詞短語>Þa_girl_touches_< 名詞短語><介詞短語>Þa_girl_touches_<冠詞><名詞><介詞短語>Þa_girl_touches_the_< 名詞><介詞短語>Þa_girl_touches_the_boy_<介詞短語>Þa_girl_touches_the_boy_<介詞>&

52、lt;復(fù)合名詞>Þa_girl_touches_the_boy_with_<復(fù)合名詞>Þa_girl_touches_the_boy_with_<冠詞><名詞>Þa_girl_touches_the_boy_with_the_<名詞>Þa_girl_touches_the_boy_with_the_flower含義是： 女孩用花碰這個男孩2.10 給出產(chǎn)生語言A=aibjck| i,j,k³0且或者i=j或者j=k的上下文無關(guān)文法。你給出的文法是歧義的嗎？為什么？解：下面是產(chǎn)生A的一個CFG

53、:S®UV|ABU®aUb|eV®cV|eA®aA|eB®bUc|e這個CFG是歧義的，因為字符串a(chǎn)bc有如下兩種不同的最左派生：SÞUVÞaUbVÞabVÞabcVÞabcSÞABÞaAVÞaVÞabVcÞabc2.11 給出識別2.10中語言A的下推自動機的非形式描述。解：其非形式描述為：此PDA有兩個非確定性的分支：一個分支先讀a，并且每讀一個a將一個a推入棧中，當(dāng)碰到b時，每讀一個b從棧中彈出一個a，若沒有a可彈出則拒絕，最后讀c且不改變

54、棧中的內(nèi)容，若此時棧為空則接受。另一個分支也是先讀a，但不改變棧中內(nèi)容，當(dāng)碰到b時，每讀一個b將一個b推入棧中，再讀c, 每讀一個c從棧中彈出一個b，若沒有a可彈出則拒絕，若c讀完后棧為空則接受。開始時，讀輸入串的字符，非確定性的選擇一個分支運行，若有一個分支接受則接受，否則拒絕。2.14 設(shè)有上下文無關(guān)文法G:S®TT|UU®0U00|#T®0T|T0|#a. 用普通的語言描述L(G)。b. 證明L(G)不是正則的。解：a. A=0i#0j#0k | i, j, k³0È0i#02i | i³0。b. 取s=0p#02p, 則對于任

55、意劃分s=xyz(|xy|£p, |y|>0), xynz=0p+i#02pÏA, 所以不是正則的。2.15 用定理2.6中給出的過程，把下述CFG轉(zhuǎn)換成等價的喬姆斯基范式文法。A®BAB|B|eB®00|e解：添加新起始變元S0, 去掉B®eS0®AS0®AA®BAB|B|eA®BAB|AB|BA|B|eB®00|eB®00去掉A®e, 去掉A®BS0®AS0®AA®BAB|AB|BA|B|BBA®BAB|AB|BA|00|BBB®00B®00去掉S0®A, 添加新變元S0®BAB|AB|BA|00|BBS0®VB|AB|BA|UU|BBA®BAB|AB|BA|00|BBA®VB|AB|BA|UU|BBB®00B®UUV®BAU®02.x 先說明如何把正則表達式直接轉(zhuǎn)換成等價得