twzheng's cppblog

『站在風(fēng)口浪尖緊握住鼠標(biāo)旋轉(zhuǎn)！』 http://www.cnblogs.com/twzheng

C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理 ::

136 隨筆 :: 78 文章 :: 353 評(píng)論 :: 0 Trackbacks

<

2008年5月

>

日

一

二

三

四

五

六

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

13

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

公告

【正在找工作，麻煩推薦，感謝！】【自我評(píng)價(jià)】 1. 資深軟件工程師/項(xiàng)目經(jīng)理，工作9年，3年經(jīng)驗(yàn)帶開(kāi)發(fā)團(tuán)隊(duì)，2年經(jīng)驗(yàn)項(xiàng)目管理，同時(shí)具備IBM大型機(jī)（z/OS390, COBOL）和開(kāi)放平臺(tái)(C#/Java) 開(kāi)發(fā)經(jīng)驗(yàn)。 2. 熟悉基金/債券業(yè)務(wù)系統(tǒng)和信用卡業(yè)務(wù)，目前是花旗軟件直屬員工，負(fù)責(zé)基金/債券系統(tǒng)。 3. 由于家人和小孩都在武漢，迫切想換工作回武漢，理想工作地是金融港和光谷軟件園。【期望職能】項(xiàng)目經(jīng)理 | 項(xiàng)目主管 | 高級(jí)軟件工程師 | 需求工程師 | 其他【期望行業(yè)】計(jì)算機(jī)軟件 | 互聯(lián)網(wǎng)/電子商務(wù) | 金融/投資/證券 | 銀行 | 信托/擔(dān)保/拍賣(mài)/典當(dāng)

留言簿(14)

隨筆分類(lèi)(130)

文章分類(lèi)(87)

新聞分類(lèi)(82)

相冊(cè)

收藏夾(40)

資料源碼

code project
codeguru
connectionstrings
devarticles
msdn web cast
sourceforge
VC知識(shí)庫(kù)
程序員聯(lián)合開(kāi)發(fā)網(wǎng)
羅索工作室
中國(guó)協(xié)議分析網(wǎng)
中國(guó)知網(wǎng)
專(zhuān)注于asp.net源碼下載

搜索

積分與排名

積分 - 490970
排名 - 41

閱讀排行榜

不確定的有窮自動(dòng)機(jī)N的確定化

[源] http://www2.gdin.edu.cn/jkx/webstudy/bianyiyuanli/fornpage/chapter03/section3/03.3.3.htm

不確定的有窮自動(dòng)機(jī)N的確定化
　　根據(jù)定義，顯然DFA是NFA的特例。對(duì)于每個(gè)NFA M，存在一個(gè)DFA M′，使得 L(M)=L(M′)。
　　對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M′，如果L(M)=L(M′)，則稱(chēng)M與M′是等價(jià)的。
　　我們將介紹一種算法，對(duì)于給定的NFA M，構(gòu)造其等價(jià)的DFA M′。

　　請(qǐng)你注意這個(gè)結(jié)論：DFA是NFA的特例
　　對(duì)每個(gè)NFA N一定存在一個(gè)DFA M，使得L(M)=L(N)。對(duì)每個(gè)NFA N存在著與之等價(jià)的DFA M。與某一NFA等價(jià)的DFA不唯一。
　　在有窮自動(dòng)機(jī)的理論里，有這樣的定理：設(shè)L為一個(gè)由不確定的有窮自動(dòng)機(jī)接受的集合，則存在一個(gè)接受L的確定的有窮自動(dòng)機(jī)。我們不對(duì)定理進(jìn)行證明，只介紹一種算法（這種算法稱(chēng)為子集法），將NFA轉(zhuǎn)換成接受同樣的語(yǔ)言的DFA。
　　為什麼對(duì)DFA如此親睞呢？因?yàn)樗男袨楹苋菀子贸绦騺?lái)模擬。
　　DFA M=（K，Σ，f，S，Z）的行為的模擬程序

　　　K:=S；
　　　c:=getchar;
　　　while c<>eof do
　　　　{K:=f(K,c);
　　　　　c:=getchar;
　　　　};
　　　if K is in Z then return (‘yes’)
　　　　else return (‘no’)

　　從NFA的矩陣表示中可以看出，表項(xiàng)通常是一個(gè)狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造的基本想法是該DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài)。該DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài)。也就是說(shuō)，在讀入輸入符號(hào)串a(chǎn)₁a₂…a_n之后，該DFA處在這樣一個(gè)狀態(tài)，該狀態(tài)表示這個(gè)NFA的狀態(tài)的一個(gè)子集T，T是從NFA的開(kāi)始狀態(tài)沿著某個(gè)標(biāo)記為a₁a₂…a_n的路徑可以到達(dá)的那些狀態(tài)。
　　為介紹算法首先定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：
　　1. 狀態(tài)集合I的ε-閉包，表示為ε-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達(dá)的狀態(tài)的集合。
　　回顧在前面章節(jié)對(duì)轉(zhuǎn)換函數(shù)的擴(kuò)充：如輸入字符是空串，則自動(dòng)機(jī)仍停留在原來(lái)的狀態(tài)上，顯然，狀態(tài)集合I的任何狀態(tài)S都屬于ε-closure(I)。
　　2. 狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)，定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。
　　我們使用圖4.4的NFA N的狀態(tài)集合來(lái)理解上述兩個(gè)運(yùn)算。

圖 4.4 NFA N

　　ε-closure(0)=｛0，1，2，4，7｝
　　即｛0，1，2，4，7｝中的任一狀態(tài)都是從狀態(tài)0經(jīng)任意條ε弧可到達(dá)的狀態(tài)，令｛0，1，2，4，7｝=A，則 move(A,a)=｛3，8｝，因?yàn)樵跔顟B(tài)0，1，2，4和7中，只有狀態(tài)2和7有a弧射出，分別到達(dá)狀態(tài)3和8。
　　而ε-closure(｛3，8｝)=｛1，2，3，4，6，7，8｝。

　　再看一個(gè)例子，對(duì)下圖所示NFA的狀態(tài)集合I的運(yùn)算

圖 4.5

　　I={1},ε-closure(I)={1,2}；
　　I={5},ε-closure(I)={5,6,2}；
　　move({1,2},a)={5,3,4}
　　ε-closure({5,3,4})={2,3,4,5,6,7,8}；

　　NFA確定化算法：假設(shè)NFA N=(K, ∑,f,K₀,K_t)按如下辦法構(gòu)造一個(gè)DFA M=(S, ∑,d,S₀,S_t)，使得L(M)=L(N)：

　　① M的狀態(tài)集S由K的一些子集組成（k的子集構(gòu)造算法見(jiàn)下頁(yè)）。用[S₁ S₂... S_j]表示S的元素，其中S₁, S₂,,... S_j是K的狀態(tài)。并且約定，狀態(tài)S₁, S₂,,... S_j是按某種規(guī)則排列的，即對(duì)于子集{S₁, S₂}={ S₂, S₁,}來(lái)說(shuō)，S的狀態(tài)就是[S₁ S₂]；
　　② M和N的輸入字母表是相同的，即是∑；
　　③ 轉(zhuǎn)換函數(shù)是這樣定義的：
　　d([S₁ S₂,... S_j],a)= [R₁R₂... R_t] 其中 {R₁,R₂,... , R_t} = e-closure(move({S₁, S₂,,... S_j},a))
　　④ S₀=e-closure(K₀)為M的開(kāi)始狀態(tài)；
　　⑤ S_t={[S_i S_k... S_e]，其中[S_i S_k... S_e]∈S且{S_i , S_k,,... S_e}∩K_t≠φ}

構(gòu)造NFA N的狀態(tài)K的子集的算法：
　　假定所構(gòu)造的子集族為C，即C= (T1, T2,,... TI),其中T1, T2,,... TI為狀態(tài)K的子集。
① 開(kāi)始，令e-closure(K0)為C中唯一成員，并且它是未被標(biāo)記的。
② while （C中存在尚未被標(biāo)記的子集T）do {
　　標(biāo)記T；
　　for 每個(gè)輸入字母a do
　　{
　　　U:= e-closure(move(T,a))；
　　　　if U不在C中 then
　　　　將U作為未標(biāo)記的子集加在C中
　　}
　}

例 3.3 應(yīng)用左面的算法對(duì)圖4.4的NFA N構(gòu)造子集，步驟如下：

　　① 首先計(jì)算ε-closure(0)，令T₀=ε-closure(0)={0，1，2，4，7}，T₀未被標(biāo)記，它現(xiàn)在是子集族C的唯一成員。
　　② 標(biāo)記T₀；令T₁=ε-closure(move(T₀,a))={1，2，3，4，6，7，8}，將T₁加入C中，T₁未被標(biāo)記。
　　令T₂=ε-closure(move (T,b))={1，2，4，5，6，7}，將T₂加入C中，它未被標(biāo)記。
　　③ 標(biāo)記T₁；計(jì)算ε-closure(move(T₁,a))，結(jié)果為{1，2，3，4，6，7，8}，即T₁，T₁已在C中。
　　計(jì)算ε-closure(move(T₁,b))，結(jié)果為{1，2，4，5，6，7，9}，令其為T(mén)₃，T₃加至C中，它未被標(biāo)記。
　　④ 標(biāo)記T₂，計(jì)算ε-closure(move(T₂,a))，結(jié)果為{1，2，3，4，6，7，8}，即T₁，T₁已在C中。
　　計(jì)算ε-closure(move(T₂,b))，結(jié)果為{1，2，4，5，6，7}，即T₂，T₂已在C中。
　　⑤ 標(biāo)記T₃，計(jì)算ε-closure(move(T₃,a))，結(jié)果為{1，2，3，4，6，7，8}，即T₁。
　　計(jì)算ε-closure(move(T₃,b))，結(jié)果為{1，2，4，5，6，7，10}，令其為T(mén)₄，加入C中，T₄未被標(biāo)記。
　　⑦ 標(biāo)記T₄，計(jì)算ε-closure(move(T₄,a))，結(jié)果為{1，2，3，4，6，7，8}，即T₁
　　計(jì)算ε-closure(move(T₄,b))結(jié)果為{1，2，4，5，6，7}，即T₂。
　　至此，算法終止共構(gòu)造了五個(gè)子集：
　　T₀={0，1，2，4，7} T₁={1，2，3，4，6，7，8}
　　T₂={1，2，4，5，6，7} T₃={1，2，4，5，6，7，9}
　　T₄={1，2，4，5，6，7，10}

　　那么圖4.4的NFA N構(gòu)造的DFA M為
　　① S={[T₀]，[T₁]，[T₂]，[T₃]，[T₄]}
　　② Σ={a,b}
　　③ D([T₀]，a)=[T₁] D([T₂]，a)=[T₁]
　　　 D([T₀]，b)=[T₂] D([T₂]，b)=[T₂]
　　　 D([T₁]，a)=[T₁] D([T₃]，a)=[T₁]
　　　 D([T₁]，b)=[T₃] D([T₃]，b)=[T₄]
　　　 D([T₄],a)=[T₁]
　　　 D([T₄]，b)=[T₂]
　　④ S₀=[T₀]
　　⑤ S_t=[T₄]
　　不妨將[T₀]，[T₁]，[T₂]，[T₃]，[T₄]重新命名，以利于書(shū)寫(xiě)，或用A，B，C，D，E或用0，1，2，3，4分別表示。若采用后者，該DFA M的狀態(tài)轉(zhuǎn)換圖如圖4.6所示。

圖 4.6 DFA M

又例：將下圖的NFA確定化

劃分子集及重新命名：

	Ia	Ib
{i,1,2} S	{1,2,3} A	{1,2,4} B
{1,2,3} A	{1,2,3,5,6,f} C	{1,2,4} B
{1,2,4} B	{1,2,3} A	{1,2,4,5,6,f} D
{1,2,3,5,6,f} C	{1,2,3,5,6,f} C	{1,2,4,6,f} E
{1,2,4,5,6,f} D	{1,2,3,6,f} F	{1,2,4,5,6,f} D
{1,2,4,6,f} E	{1,2,3,6,f} F	{1,2,4,5,6,f} D
{1,2,3,6,f} F	{1,2,3,5,6,f} C	{1,2,4,6,f} E

確定化后的自動(dòng)機(jī)：

posted on 2007-04-03 22:20 譚文政閱讀(1874) 評(píng)論(1) 編輯收藏引用所屬分類(lèi): 基礎(chǔ)知識(shí)

評(píng)論

# re: 不確定的有窮自動(dòng)機(jī)N的確定化 2011-05-12 09:44 歸地方

圖片失效鳥(niǎo) 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。


相關(guān)文章: Win XP系統(tǒng)任務(wù)欄實(shí)用技巧總集 [轉(zhuǎn)]電子書(shū)籍制作工具軟件大全 WAV轉(zhuǎn)MP3格式最簡(jiǎn)單的方法 C#Windows控件的焦點(diǎn)事件順序 C# 怎么顯示中文格式的日期、星期幾 [轉(zhuǎn)] 網(wǎng)頁(yè)設(shè)計(jì)者值得一去的地方！ Word表格及Excel中斜線(xiàn)表頭的繪制方法。 [轉(zhuǎn)] 深入剖析XP的BOOT.INI 什么是uri和url? 存儲(chǔ)類(lèi)說(shuō)明符：auto,register, extern mutable 和static

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品