第一部分習(xí)習(xí)題

1、第一章習(xí)題1.書(shū)p36 解：（a） 首尾均為0的二進(jìn)制串（b） 0，1組成的二進(jìn)制串，包括空串（c） 倒數(shù)第3位為0的二進(jìn)制串（d） 包含且僅包含3個(gè)1的二進(jìn)制串（e） 1的個(gè)數(shù)和0的個(gè)數(shù)均為偶數(shù)的二進(jìn)制串 為檢驗(yàn)是否確切的描述，需要通過(guò)正反兩方面來(lái)思考。反過(guò)來(lái)還需要考慮，任何出偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的串是否都在這個(gè)語(yǔ)言中。這實(shí)際上是問(wèn)，每個(gè)這樣的串，其結(jié)構(gòu)是否都符合(e)中正規(guī)式所做的刻畫(huà)。我們可以這樣敘述由偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的串，從左向右，每?jī)蓚€(gè)字符一組地考察，它 1由若干個(gè)(強(qiáng)調(diào)一下，可以是零個(gè))00或11開(kāi)始(這由正規(guī)式(00|11)*描述)；2一旦出現(xiàn)1個(gè)01或10，那么經(jīng)過(guò)若干

2、個(gè)00或11后，一定會(huì)出現(xiàn)1個(gè)01或10。這第二個(gè)01或10的后而可能還有若干個(gè)00或11，一直到串的結(jié)束，或者到再次出現(xiàn)01或者10為止。如果串沒(méi)有結(jié)束的話(huà)，就是重復(fù)出現(xiàn)這里所描述的結(jié)構(gòu)(所以，這由(01|10)(00|11)*(01|10)(00|11)*)*描述)。那么這種描述是否是最簡(jiǎn)的呢滿(mǎn)足要求的最簡(jiǎn)單的串有：(1)00(2)11(3) (01|10)(00|11)*(01|10)它們?nèi)我舛啻蔚闹貜?fù)構(gòu)成的中仍然滿(mǎn)足要求因此最簡(jiǎn)的串可以寫(xiě)成(00|11|(01|10)(00|11)*(01|10)*。2.寫(xiě)出語(yǔ)言“由偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的所有0和1的串”的正規(guī)定義。分析 有了上一題的

3、結(jié)果，這個(gè)問(wèn)題應(yīng)該容易解決。首先給上一題的正規(guī)式起個(gè)名字： even_0_even_1® ( 00 | 11 | (01|10) (00|11)* (01|10) )* 對(duì)于偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的串，其第一個(gè)字符可能是0或1。 1如果是1，那么剩下的部分一定是偶數(shù)個(gè)0和偶數(shù)個(gè)1（即1 even_0_even_1）。 2如果是0，那么經(jīng)過(guò)若干個(gè)偶數(shù)個(gè)0或偶數(shù)個(gè)1，一定會(huì)出現(xiàn)一個(gè)01或10，才能保證0的個(gè)數(shù)是偶數(shù)，1的個(gè)數(shù)是奇數(shù)。若串還沒(méi)有結(jié)束，剩余部分一定是偶數(shù)個(gè)0和偶數(shù)個(gè)1。 這樣，正確的正規(guī)定義是： 答案 even_0_even_1® (00 | 11 | (01|10

4、) (00|11)* (01|10) )* even_0_odd_1® 1 even_0_even_1 | 0 even_0_even_1 (01|10) even_0_even_13寫(xiě)出語(yǔ)言“所有相鄰數(shù)字都不相同的數(shù)字串”的正規(guī)定義。答案 no_0-8 ® 9no_0-7 ®(8 | no_0-8 8 ) (no_0-8 8 )* (no_0-8 | e ) | no_0-8no_0-6®(7 | no_0-7 7 ) (no_0-7 7 )* (no_0-7 | e ) | no_0-7no_0-5 ®(6 | no_0-6 6 ) (no

5、_0-6 6 )* (no_0-6 | e ) | no_0-6no_0-4 ®(5 | no_0-5 5 ) (no_0-5 5 )* (no_0-5 | e ) | no_0-5no_0-3®(4 | no_0-4 4 ) (no_0-4 4 )* (no_0-4 | e ) | no_0-4no_0-2®(3 | no_0-3 3 ) (no_0-3 3 )* (no_0-3 | e ) | no_0-3no_0-1 ®(2 | no_0-2 2 ) (no_0-2 2 )* (no_0-2 | e ) | no_0-2no_0 ® (1

6、 | no_0-1 1 ) (no_0-1 1 )* (no_0-1 | e ) | no_0-1answer® (0 | no_0 0 ) (no_0 0 )* (no_0 | e ) | no_0分析 本題和上面一樣，關(guān)鍵是找到一種合適的看待這種句子結(jié)構(gòu)的觀點(diǎn)。我們的觀點(diǎn)是這樣，每個(gè)這樣的句子由若干個(gè)0把它分成若干段，如123可以看成123, 0, 313571, 0, 6678, 0, 3559, 0, 123由0隔開(kāi)的每一段，如313571，它不含0，并且又可以看成是由若干個(gè)1把它分成若干段。如此下去，就能找到該語(yǔ)言的正規(guī)定義。按這個(gè)思路，上面的正規(guī)定義應(yīng)該逆序看。answe

7、r® (0 | no_0 0 ) (no_0 0 )* (no_0 | e ) | no_0表示一個(gè)句子由若干個(gè)0分成若干段，特殊情況是整個(gè)句子不含0。在這個(gè)正規(guī)定義中，所引用的no_0表示不含0的串，它的定義和這個(gè)定義的形式一樣，因?yàn)榇男问绞且粯拥?，只不過(guò)沒(méi)有數(shù)字0。所以有no_0 ® (1 | no_0-1 1 ) (no_0-1 1 )* (no_0-1 | e ) | no_0-1其中no_0-1表示不含0和1的串。依此類(lèi)推，最后no_0-8是表示不含0, , 8的沒(méi)有重復(fù)數(shù)字的串，它只可能是單個(gè)9。4. 將圖的DFA極小化。aa開(kāi)始0123abbbbb4圖 一個(gè)

8、DFA012bbbb4aa開(kāi)始圖 最簡(jiǎn)DFA答案 最簡(jiǎn)DFA見(jiàn)圖。分析 本題要注意的是，在使用極小化算法前，一定要檢查一下，看狀態(tài)轉(zhuǎn)換函數(shù)是否為全函數(shù)，即每個(gè)狀態(tài)對(duì)每個(gè)輸入符號(hào)都有轉(zhuǎn)換。若不是全函數(shù)，需加入死狀態(tài)，然后再用極小化算法。最后再把死狀態(tài)刪除。有些教材上沒(méi)有強(qiáng)調(diào)這一點(diǎn)，有的習(xí)題解上的示例甚至忽略了這一點(diǎn)，本題將告訴你，這一點(diǎn)是重要的。本題加入死狀態(tài)5后的狀態(tài)轉(zhuǎn)換圖見(jiàn)圖。0123aabbabbb開(kāi)始45aaa, b圖 加入死狀態(tài)后的DFA使用極小化算法，先把狀態(tài)集分成非接受狀態(tài)集0, 1, 2, 3, 5和接受狀態(tài)集4這兩個(gè)子集。1集合4不能再分解，我們看集合0, 1, 2, 3, 5

9、。move (0, 1, 2, 3, 5, a) = 1, 2, 5move (0, 1, 2, 3, 5, b) = 3, 4, 5由于b 轉(zhuǎn)換的結(jié)果3, 4, 5不是最初劃分的某個(gè)集合的子集，因此0, 1, 2, 3, 5需要再分，由于狀態(tài)1和狀態(tài)2的b轉(zhuǎn)換都到狀態(tài)4。因此狀態(tài)集合的進(jìn)一步劃分是：1, 2，0, 3, 5和42由于move (1, 2, a) = 2, 5move (1, 2, b) = 4move (0, 3, 5, a) = 1, 5move (0, 3, 5, b) = 3, 5顯然1, 2和0, 3, 5需要再分，分別分成：1和2以及0, 3和53由于move (0

10、, 3, a) = 1move (0, 3, b) = 3因此不需要再分。這樣狀態(tài)0和狀態(tài)3合并成一個(gè)狀態(tài)，我們?nèi)?為代表，再刪去死狀態(tài)5，就得到該題的結(jié)果。如果不加死狀態(tài)，我們來(lái)看一下極小化算法的結(jié)果。最初的劃分是0, 1, 2, 3和4。1狀態(tài)集合的進(jìn)一步劃分是：1, 2，0, 3和401bbaastarta4圖 一個(gè)不正確的結(jié)果2忽略了死狀態(tài)的影響，會(huì)認(rèn)為它們都不需要再分，此時(shí)得到的DFA如圖。顯然，它和原來(lái)的DFA不等價(jià)。5. 一個(gè)C語(yǔ)言編譯器編譯下面的函數(shù)時(shí)，報(bào)告parse error before else。這是因?yàn)閑lse的前面少了一個(gè)分號(hào)。但是如果第一個(gè)注釋/* then pa

11、rt */誤寫(xiě)成/* then part那么該編譯器發(fā)現(xiàn)不了遺漏分號(hào)的錯(cuò)誤。這是為什么long gcd(p,q)long p,q; if (p%q = 0)/* then part */return q else/* else part */return gcd(q, p%q);答案 此時(shí)編譯器認(rèn)為/* then part return q else/* else part */是程序的注釋?zhuān)虼怂豢赡茉侔l(fā)現(xiàn)else 前面的語(yǔ)法錯(cuò)誤。分析 這是注釋用配對(duì)括號(hào)表示時(shí)的一個(gè)問(wèn)題。注釋是在詞法分析時(shí)忽略的，而詞法分析器對(duì)程序采取非常局部的觀點(diǎn)。當(dāng)進(jìn)入第一個(gè)注釋后，詞法分析器忽略輸入符號(hào)，一直到出現(xiàn)

12、注釋的右括號(hào)為止，由于第一個(gè)注釋缺少右括號(hào)，所以詞法分析器在讀到第二個(gè)注釋的右括號(hào)時(shí)，才認(rèn)為第一個(gè)注釋處理結(jié)束。為克服這個(gè)問(wèn)題，后來(lái)的語(yǔ)言一般都不用配對(duì)括號(hào)來(lái)表示注釋。例如Ada語(yǔ)言的注釋始于雙連字符（-），隨行的結(jié)束而終止。如果用Ada語(yǔ)言的注釋格式，那么上面函數(shù)應(yīng)寫(xiě)成long gcd(p,q)long p,q; if (p%q = 0)- then part return q else- else part return gcd(q, p%q);6. 為正規(guī)式 (a|b)* a (a|b) (a|b) 構(gòu)造NFA。答案 該正規(guī)式的狀態(tài)轉(zhuǎn)換圖見(jiàn)圖。開(kāi)始abaabab1234圖 接受正規(guī)式(a

13、|b)* a (a|b) (a|b)的NFA7. 用狀態(tài)轉(zhuǎn)換圖表示接收(a|b)*aa 的DFA。該正規(guī)式表示的語(yǔ)言是，字母表上最后兩個(gè)字符都是a的串的集合。抓住這個(gè)特點(diǎn)，我們首先畫(huà)出構(gòu)造過(guò)程中的第一步，見(jiàn)圖。它表明最簡(jiǎn)單的句子是aa。開(kāi)始aa012圖 構(gòu)造過(guò)程的第一步 然后，因?yàn)樵诘谝粋€(gè)a前可以有若干個(gè)b，因此狀態(tài)0有到自身的b轉(zhuǎn)換。在最后兩個(gè)字符都是a的串的末尾添加若干個(gè)a，能夠保持串的這個(gè)性質(zhì)，因此狀態(tài)2有到自身的a轉(zhuǎn)換。這樣我們有圖。開(kāi)始aaab012圖 構(gòu)造過(guò)程的第二步最后，在狀態(tài)1和狀態(tài)2碰到b時(shí)，前面剛讀過(guò)的a，不管連續(xù)有多少個(gè)，都不可能作為句子結(jié)尾的那兩個(gè)字符a，因此狀態(tài)3和狀

14、態(tài)2的b轉(zhuǎn)換回到狀態(tài)0。所有狀態(tài)的a轉(zhuǎn)換和b轉(zhuǎn)換都己給出，這就得到最后結(jié)果。開(kāi)始aaab012bb圖 構(gòu)造結(jié)果練習(xí)：構(gòu)造 DFA，接受 0和1的個(gè)數(shù)都是偶數(shù)的二進(jìn)制串。eg: 0011, 00, 1100, 1010, 111100解：狀態(tài)0：偶數(shù)個(gè)0偶數(shù)個(gè)1狀態(tài)1：奇數(shù)個(gè)1偶數(shù)個(gè)0 11001100狀態(tài)2：奇數(shù)個(gè)0偶數(shù)個(gè)1狀態(tài)3：奇數(shù)個(gè)0奇數(shù)個(gè)1練習(xí)（a）解：兩種方法：方法一：（1） 根據(jù)算法構(gòu)造NFA（2） 根據(jù)算法將NFAàDFA（3） 根據(jù)算法將DFA簡(jiǎn)化方法二：ABCDabababab012aa, ba, b（1） 直接構(gòu)造NFA（2） 根據(jù)算法將NFAàDFAA=0B=0,1C=0,1,2D=0,2abABABCDCCDDBA（3） 根據(jù)算法將DFA簡(jiǎn)化a, 劃分狀態(tài)集A, B，C,Db, A,B面臨字母a時(shí)轉(zhuǎn)到B,C，由于B,C分屬于不同的狀態(tài)集，故此狀態(tài)集A,B需要進(jìn)一步劃分成ABc,考慮C,D,它面臨字母a時(shí)轉(zhuǎn)到B,C，而B(niǎo),C分屬于不同的狀態(tài)集，故此狀態(tài)集C,D需要進(jìn)一步劃分成C