[工學(xué)]形式語(yǔ)言與自動(dòng)機(jī)07章正則語(yǔ)言的性質(zhì)(編輯修改稿)
2024-11-14 23:57 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 1 00* 1 00*11 00*10 q1 q2 X Y ? 00*1 并弧 q0 1 0 0 00* + 00*1 1 00*11+1 00*10 q1 q2 X Y ? 去掉狀態(tài) q0 ?使用“去狀態(tài) 2”， q = q2 | q1 | X， p= q0 ， t=q1 0 00* + 00*1 (00*11+1)1*0 00*10 q1 q2 X Y 11*0 1*0 并弧 0 00* + 00*1 00*10+(00*11+1)1*0 q1 q2 X Y 11*0 1*0 去掉狀態(tài) q1 00* + 00*1 (00*10+(00*11+1)1*0)(11*0)*0 q2 X Y 1*0(11*0)*0 ?使用“去狀態(tài) 2”， q = q2 | X， p= q0 ， t=q2 去掉狀態(tài) q2 X Y 1*0(11*0)*0((00*10+(00*11+1)1*0)(11*0)*0)* (00* + 00*1) ?使用“去狀態(tài) 2” 討論 ?在哪些情況需要使用 “ 去狀態(tài) 3”？ ?如何選擇去狀態(tài)順序減少工作量 ？ 說(shuō)明 ?如果刪除狀態(tài)的順序不一致 ， 最后得到的正則表達(dá)式可能在形式上不一樣 ， 但它們都是等價(jià)的；而且刪除狀態(tài)和并弧操作也沒(méi)有絕對(duì)的先后順序 ， 一般地 ， 在狀態(tài)圖的處理過(guò)程中 ， 優(yōu)先地執(zhí)行并弧操作 ， 會(huì)使后繼的刪除狀態(tài)簡(jiǎn)單一些 ， 因?yàn)樵黾拥幕?huì)少一些 。 ?當(dāng) FSAM的接收狀態(tài)都是不可到達(dá)狀態(tài)時(shí) ， 狀態(tài)轉(zhuǎn)換圖中肯定不存在從開(kāi)始狀態(tài)到某個(gè)接收狀態(tài)的路；使用 “ 圖上作業(yè) ” 方法 ， 最終會(huì)去掉除狀態(tài) X和狀態(tài) Y以外的所有狀態(tài)和弧 ， 這種情況下 ， 對(duì)應(yīng)的正則表達(dá)式為 Φ。 說(shuō)明 (續(xù) ) ?不計(jì)算自身到自身的弧 ， 如果狀態(tài) q的入度為 n，出度為 m， 則將狀態(tài) q及相關(guān)的弧去掉之后 ，需要增加 n*m條新弧 。 ?對(duì)于操作步驟進(jìn)行歸納假設(shè) ， 不難證明 “ 圖上作業(yè) ” 方法的正確性 。 ?按照 “ 圖上作業(yè) ” 的方法 ， 最后 ， 沒(méi)有將標(biāo)記為 X和 Y的兩個(gè)狀態(tài)去掉 。 ?“ 圖上作業(yè) ” 的方法 ， 也可以當(dāng)作一個(gè)算法 ，可以利用計(jì)算機(jī)實(shí)現(xiàn) ， 有興趣的讀者可以進(jìn)行試驗(yàn) 。 作業(yè) ?求與圖 611自動(dòng)機(jī)等價(jià)的正則表達(dá)式 。 正則語(yǔ)言的等價(jià)模型 ?正則語(yǔ)言有 5種等價(jià)模型：正則文法 （ 右線性文法 ） RG， 正則表達(dá)式 RE、 確定的有限狀態(tài)自動(dòng)機(jī) FSAM， 不確定的有限狀態(tài)自動(dòng)機(jī) ?NDAM， 帶 ?動(dòng)作的有限狀態(tài)自動(dòng)機(jī) ? NDAM。 ?正則語(yǔ)言的 5種等價(jià)模型的轉(zhuǎn)換關(guān)系可以用圖 728表
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1