構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第1頁
構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第2頁
構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第3頁
構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第4頁
構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第5頁
已閱讀5頁，還剩2頁未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡介

1、構(gòu)造正規(guī)式相應(yīng)的DFA精品資料構(gòu)造正規(guī)式相應(yīng)的 DFA : 1（0|1）*101按照以下三步：（1）由正規(guī)表達(dá)式構(gòu)造轉(zhuǎn)換系統(tǒng)（NFA）（2） 由轉(zhuǎn)換系統(tǒng)（NFA ）構(gòu)造確定的有窮自動(dòng)機(jī) 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。對(duì)于r1，有：對(duì)于r2，有:0,1對(duì)于r3，有:因此，與正規(guī)式r=r1r2r3相對(duì)應(yīng)的NFA如圖所示為:展

2、開為:(2)將NFA轉(zhuǎn)換成DFA采用子集法，即DFA的每個(gè)狀態(tài)對(duì)應(yīng)NFA的一個(gè)狀態(tài)集合。構(gòu)造DFA的狀態(tài)集 C,假定 C=TO, T1,Ti，集中 TO=&closure (X),對(duì)于任何 aETi= £-closure (Move (Ti, a)。TiTi0Ti1A0T0A1 , A2 , A3=T1A1 , A2, A3T1A2 , A3=T2A2 , A4 , A3=T3A2 , A3T2A2 , A3=T2r A2 , A4 , A3=T3A2 , A3, A4T3A2 , A5 , A3=T4A2 , A4 , A3=T3A2 , A3 , A5T4A2 , A3=T2r A2 , A4 , A6 , A3=T6A2 , A3 , A4 , A6 T5A2 , A5 , A3=T4A2 , A4 , A3=T3DFA的狀態(tài)轉(zhuǎn)換圖(3)化簡DFA :分割法，把DFA的狀態(tài)集分成一些不想交的子集，使得不同的兩子集的狀態(tài)是可區(qū)別的，同一子集的狀態(tài)是等價(jià)的。首先，將狀態(tài)分成兩個(gè)子集：一個(gè)由終態(tài)組成，一個(gè)由非態(tài)組成：TO, T1, T2, T3，T4 T5TO，T1, T2, T3 T4 T5 TO, T1 , T2 T3 T4 T5TO T1 , T2 T3 T4 T5在等價(jià)狀態(tài)子集T1，T2中選狀態(tài)T2做代表，消去其他狀態(tài)T1,把從消去狀態(tài)T1射出和射入的

溫馨提示

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

評(píng)論

0/150

提交評(píng)論