2008年下半年計算機軟件設(shè)計師考試考前秋點兵

　　供選擇的答案：

　　(28)A.以1開頭的二進制代碼串組成的集合

　　B.以1結(jié)尾的二進制代碼串組成的集合

　　C.包含偶數(shù)個0的二進制代碼串組成的集合

　　D.包含奇數(shù)個0的二進制代碼串組成的集合

　　(29)A.1*0(0|1)* B.((0|1*0)*1*)*

　　C.1*((0|1)0)* D.(1*(01*0)*)*

　　首先，我對狀態(tài)圖做一些說明。在狀態(tài)轉(zhuǎn)換圖中，末端沒有狀態(tài)連接的“→”所指向的結(jié)點為初態(tài)結(jié)點，而終態(tài)用雙環(huán)圈表示，顯然，該題中q0既是初態(tài)又是終態(tài)，那么該DFA顯然能識別空串，當(dāng)處于q0時輸入0便轉(zhuǎn)換到q1，而當(dāng)處于q1時輸入0又回到q0，并且在q0或q1狀態(tài)連續(xù)輸入n≥0個1仍回到原狀態(tài)，因此，該DFA識別的串是包含偶數(shù)個0的二進制代碼串，即在偶數(shù)個0之間或前后可插入任意個1的串，如ε、00、010、10101、1011011、1001101101。

　　對于正規(guī)式，首先來了解幾個符號的意思：“*”號的意思，在正規(guī)式中，它表示任意自我連接，比如，a*表示n≥0個a...，而(ab)*表示n≥0個ab相連： ababab...;“|”表示或;“●”表示連接，常省略，如a●b=ab。

　　如果某有窮自動機所能識別的字符串集跟某正規(guī)式對應(yīng)的正規(guī)集相等，則稱兩者等價。將有窮自動機轉(zhuǎn)M化為與其等價的正規(guī)式R的步驟為：

　　首先，在M的轉(zhuǎn)換圖上加進兩個狀態(tài)x和y，從x用標(biāo)有ε的弧連接到M的所有初態(tài)結(jié)點，從M的所有終態(tài)結(jié)點用標(biāo)有ε的弧連接到y(tǒng)，從而形成一個新的有窮自動機，記為M’，它只有一個初態(tài)x和一個終態(tài)y，顯然L(M)=L(M’), L(M)表示M所能接受的字符串集。