構(gòu)造正規(guī)式相應(yīng)的DFA_第1頁
構(gòu)造正規(guī)式相應(yīng)的DFA_第2頁
構(gòu)造正規(guī)式相應(yīng)的DFA_第3頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、構(gòu)造正規(guī)式相應(yīng)的DFA：1(0|1)*101依據(jù)以下三步：（1）由正規(guī)表達式構(gòu)造轉(zhuǎn)換系統(tǒng)（NFA）（2）由轉(zhuǎn)換系統(tǒng)（NFA）構(gòu)造確定的有窮自動機DFA（3）DFA的最小化答：（1）首先構(gòu)造與正規(guī)式1（0|1）*101相應(yīng)的NFA，然后再將NFA確定化。為正規(guī)式構(gòu)造NFA的方法為“語法制導(dǎo)”法，即依據(jù)正規(guī)式的語法構(gòu)造來構(gòu)造。首先將正規(guī)式r=1（0|1）*101分解成r=r1,r2r3，其中：r1=1，r2=（0|1）*，r3=101。對于r1，有：XA1對于r2，有：A0,1對于r3，有：XBCY110因此，與正規(guī)式r=r1r2r3相對應(yīng)的NFA如圖所示為：A0,1X1BCY110開放為：A30

2、X1BCY110A2A11（2）將NFA轉(zhuǎn)換成DFA接受子集法，即DFA的每個狀態(tài)對應(yīng)NFA的一個狀態(tài)集合。構(gòu)造DFA的狀態(tài)集C，假定C=T0，T1，Ti，集中T0=-closure（X），對于任何aTi=-closure（Move（Ti，a）。TiTi0Ti1A0 T0A1，A2，A3=T1A1，A2，A3 T1A2，A3=T2A2，A4，A3=T3A2，A3 T2A2，A3=T2A2，A4，A3=T3A2，A3，A4 T3A2，A5，A3=T4A2，A4，A3=T3A2，A3，A5 T4A2，A3=T2A2，A4，A6，A3=T6A2，A3，A4，A6 T5A2，A5，A3=T4A2，A4，A3=T3DFA的狀態(tài)轉(zhuǎn)換圖T0T1T2T3T4T511111100000（3）化簡DFA：分割法，把DFA的狀態(tài)集分成一些不想交的子集，使得不同的兩子集的狀態(tài)是可區(qū)分的，同一子集的狀態(tài)是等價的。首先，將狀態(tài)分成兩個子集：一個由終態(tài)組成，一個由非態(tài)組成：T0，T1，T2，T3，T4 T5 T0，T1，T2，T3 T4 T5 T0，T1，T2 T3 T4 T5 T0 T1，T2 T3 T4 T5在等價狀態(tài)子集T1，T2中選狀態(tài)T2做代表，消去其他狀態(tài)T1，把從消去狀態(tài)T1射出和射入的弧都

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論