構(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ù)免費閱讀

下載本文檔

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

文檔簡介

1、構(gòu)造正規(guī)式相應(yīng)的DFA精品資料構(gòu)造正規(guī)式相應(yīng)的 DFA : 1(0|1)*101按照以下三步:(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,有:對于r2,有:0,1對于r3,有:因此,與正規(guī)式r=r1r2r3相對應(yīng)的NFA如圖所示為:展

2、開為:(2)將NFA轉(zhuǎn)換成DFA采用子集法,即DFA的每個狀態(tài)對應(yīng)NFA的一個狀態(tài)集合。構(gòu)造DFA的狀態(tài)集 C,假定 C=TO, T1,Ti,集中 TO=&closure (X),對于任何 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)是等價的。首先,將狀態(tài)分成兩個子集:一個由終態(tài)組成,一個由非態(tài)組成:TO, T1, T2, T3,T4 T5TO,T1, T2, T3 T4 T5 TO, T1 , T2 T3 T4 T5TO 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)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論