2008年下半年計(jì)算機(jī)軟件設(shè)計(jì)師考試考前秋點(diǎn)兵

　　供選擇的答案：

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

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

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

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

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

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

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

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

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

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