![構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第1頁](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/7e2b1a12-30a3-4931-bb31-0f43560056f6/7e2b1a12-30a3-4931-bb31-0f43560056f61.gif)
![構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第2頁](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/7e2b1a12-30a3-4931-bb31-0f43560056f6/7e2b1a12-30a3-4931-bb31-0f43560056f62.gif)
![構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第3頁](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/7e2b1a12-30a3-4931-bb31-0f43560056f6/7e2b1a12-30a3-4931-bb31-0f43560056f63.gif)
![構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第4頁](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/7e2b1a12-30a3-4931-bb31-0f43560056f6/7e2b1a12-30a3-4931-bb31-0f43560056f64.gif)
![構(gòu)造正規(guī)式相應(yīng)的DFA復(fù)習(xí)過程_第5頁](http://file3.renrendoc.com/fileroot_temp3/2021-12/16/7e2b1a12-30a3-4931-bb31-0f43560056f6/7e2b1a12-30a3-4931-bb31-0f43560056f65.gif)
版權(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- GB/Z 44938.1-2024機械電氣安全第1部分:用于保護人員安全的傳感器
- racemic-8-Hydroxy-cannabichromene-生命科學(xué)試劑-MCE-7832
- Mouse-Laminin-生命科學(xué)試劑-MCE-7265
- 二零二五年度雙方2025年度智能機器人研發(fā)團隊用工合同
- 2025年度自媒體合伙人合同版:短視頻平臺網(wǎng)紅孵化與推廣合同
- 防震防火的應(yīng)急預(yù)案
- 上海市商業(yè)租賃合同
- 產(chǎn)業(yè)基地設(shè)施維護合同
- 上海市汽車租賃合同模版正式版
- 個人住宅購買合同定金協(xié)議
- 2022屆“一本、二本臨界生”動員大會(2023.5)
- 《簡單教數(shù)學(xué)》讀書-分享-
- 口腔頜面外科學(xué) 功能性外科
- 脊椎動物學(xué)知識點歸納各綱特征
- GB/T 27476.5-2014檢測實驗室安全第5部分:化學(xué)因素
- 金屬非金屬礦山重大生產(chǎn)安全事故隱患判定標(biāo)準(zhǔn)課件
- 四年級上冊數(shù)學(xué)課件-一般應(yīng)用題 全國通用(共26張PPT)
- 肝臟炎性假瘤的影像學(xué)表現(xiàn)培訓(xùn)課件
- 國家行政機關(guān)公文格式課件
- 業(yè)務(wù)員回款考核辦法
- 急性心梗的護理業(yè)務(wù)學(xué)習(xí)課件
評論
0/150
提交評論