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