第一部分習(xí)題

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

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

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

4、1|10) (00|11)* (01|10) )* even_0_odd_1® 1 even_0_even_1 | 0 even_0_even_1 (01|10) even_0_even_13寫出語言“所有相鄰數(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 )

5、 (no_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-4推薦精選no_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 &

6、#174; (1 | 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)的觀點。我們的觀點是這樣，每個這樣的句子由若干個0把它分成若干段，如123031357106678035590123可以看成123, 0, 313571, 0, 6678, 0, 3559, 0, 123由0隔開的每一段，如313571，它不含0，并且又可以看成是由若干個1把它分成若干段。如此下去，就能找到該語言的

7、正規(guī)定義。按這個思路，上面的正規(guī)定義應(yīng)該逆序看。answer® (0 | no_0 0 ) (no_0 0 )* (no_0 | e ) | no_0表示一個句子由若干個0分成若干段，特殊情況是整個句子不含0。在這個正規(guī)定義中，所引用的no_0表示不含0的串，它的定義和這個定義的形式一樣，因為串的形式是一樣的，只不過沒有數(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的串。依此類推，最后no_0-8是表示不含0, , 8的沒有重復(fù)數(shù)字的串，它只可能是單個9。4.

8、將圖1.13的DFA極小化。aa開始0123abbbbb4圖1.1 一個DFA012bbbb4aa開始圖1.2 最簡DFA答案 最簡DFA見圖1.2。分析 本題要注意的是，在使用極小化算法前，一定要檢查一下，看狀態(tài)轉(zhuǎn)換函數(shù)是否為全函數(shù)，即每個狀態(tài)對每個輸入符號都有轉(zhuǎn)換。若不是全函數(shù)，需加入死狀態(tài)，然后再用極小化算法。最后再把死狀態(tài)刪除。有些教材上沒有強(qiáng)調(diào)這一點，有的習(xí)題解上的示例甚至忽略了這一點，本題將告訴你，這一點是重要的。本題加入死狀態(tài)5后的狀態(tài)轉(zhuǎn)換圖見圖1.3。推薦精選0123aabbabbb開始45aaa, b圖1.3 加入死狀態(tài)后的DFA使用極小化算法，先把狀態(tài)集分成非接受狀態(tài)集0,

9、 1, 2, 3, 5和接受狀態(tài)集4這兩個子集。1集合4不能再分解，我們看集合0, 1, 2, 3, 5。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不是最初劃分的某個集合的子集，因此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)

10、 = 3, 5顯然1, 2和0, 3, 5需要再分，分別分成：1和2以及0, 3和53由于move (0, 3, a) = 1move (0, 3, b) = 3因此不需要再分。這樣狀態(tài)0和狀態(tài)3合并成一個狀態(tài)，我們?nèi)?為代表，再刪去死狀態(tài)5，就得到該題的結(jié)果。如果不加死狀態(tài)，我們來看一下極小化算法的結(jié)果。最初的劃分是0, 1, 2, 3和4。1狀態(tài)集合的進(jìn)一步劃分是：1, 2，0, 3和401bbaastarta4圖1.4 一個不正確的結(jié)果2忽略了死狀態(tài)的影響，會認(rèn)為它們都不需要再分，此時得到的DFA如圖1.4。顯然，它和原來的DFA不等價。5. 一個C語言編譯器編譯下面的函數(shù)時，報告par

11、se error before else。這是因為else的前面少了一個分號。但是如果第一個注釋/* then part */推薦精選誤寫成/* then part那么該編譯器發(fā)現(xiàn)不了遺漏分號的錯誤。這是為什么？long gcd(p,q)long p,q; if (p%q = 0)/* then part */return q else/* else part */return gcd(q, p%q);答案 此時編譯器認(rèn)為/* then part return q else/* else part */是程序的注釋，因此它不可能再發(fā)現(xiàn)else 前面的語法錯誤。分析 這是注釋用配對括號表示時的一

12、個問題。注釋是在詞法分析時忽略的，而詞法分析器對程序采取非常局部的觀點。當(dāng)進(jìn)入第一個注釋后，詞法分析器忽略輸入符號，一直到出現(xiàn)注釋的右括號為止，由于第一個注釋缺少右括號，所以詞法分析器在讀到第二個注釋的右括號時，才認(rèn)為第一個注釋處理結(jié)束。為克服這個問題，后來的語言一般都不用配對括號來表示注釋。例如Ada語言的注釋始于雙連字符（-），隨行的結(jié)束而終止。如果用Ada語言的注釋格式，那么上面函數(shù)應(yīng)寫成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

13、|b)* a (a|b) (a|b) 構(gòu)造NFA。答案 該正規(guī)式的狀態(tài)轉(zhuǎn)換圖見圖1.5。推薦精選開始abaabab1234圖1.5 接受正規(guī)式(a|b)* a (a|b) (a|b)的NFA7. 用狀態(tài)轉(zhuǎn)換圖表示接收(a|b)*aa 的DFA。該正規(guī)式表示的語言是，字母表上最后兩個字符都是a的串的集合。抓住這個特點，我們首先畫出構(gòu)造過程中的第一步，見圖1.6。它表明最簡單的句子是aa。開始aa012圖1.6 構(gòu)造過程的第一步 然后，因為在第一個a前可以有若干個b，因此狀態(tài)0有到自身的b轉(zhuǎn)換。在最后兩個字符都是a的串的末尾添加若干個a，能夠保持串的這個性質(zhì)，因此狀態(tài)2有到自身的a轉(zhuǎn)換。這樣我們有

14、圖1.7。開始aaab012圖1.7 構(gòu)造過程的第二步最后，在狀態(tài)1和狀態(tài)2碰到b時，前面剛讀過的a，不管連續(xù)有多少個，都不可能作為句子結(jié)尾的那兩個字符a，因此狀態(tài)3和狀態(tài)2的b轉(zhuǎn)換回到狀態(tài)0。所有狀態(tài)的a轉(zhuǎn)換和b轉(zhuǎn)換都己給出，這就得到最后結(jié)果。開始aaab012bb圖1.8 構(gòu)造結(jié)果練習(xí)：構(gòu)造 DFA，接受 0和1的個數(shù)都是偶數(shù)的二進(jìn)制串。推薦精選eg: 0011, 00, 1100, 1010, 111100解：狀態(tài)0：偶數(shù)個0偶數(shù)個1狀態(tài)1：奇數(shù)個1偶數(shù)個0 11001100狀態(tài)2：奇數(shù)個0偶數(shù)個1狀態(tài)3：奇數(shù)個0奇數(shù)個1練習(xí)2.12（a）解：兩種方法：方法一：（1） 根據(jù)算法2.4構(gòu)造

15、NFA（2） 根據(jù)算法2.2將NFAàDFA（3） 根據(jù)算法2.3將DFA簡化方法二：ABCDabababab012aa, ba, b（1） 直接構(gòu)造NFA（2） 根據(jù)算法2.2將NFAàDFAA=0B=0,1C=0,1,2D=0,2abABABCDCCDDBA（3） 根據(jù)算法2.3將DFA簡化a, 劃分狀態(tài)集A, B，C,Db, A,B面臨字母a時轉(zhuǎn)到B,C，由于B,C分屬于不同的狀態(tài)集，故此狀態(tài)集A,B需要進(jìn)一步劃分成ABc,考慮C,D,它面臨字母a時轉(zhuǎn)到B,C，而B,C分屬于不同的狀態(tài)集，故此狀態(tài)集C,D需要進(jìn)一步劃分成CD推薦精選由上面可以知道，最簡的DFA包含四個狀態(tài)集AB