twzheng's cppblog

『站在風口浪尖緊握住鼠標旋轉！』 http://www.cnblogs.com/twzheng

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

136 隨筆 :: 78 文章 :: 353 評論 :: 0 Trackbacks

<

2007年4月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

公告

留言簿(14)

隨筆分類(130)

文章分類(87)

新聞分類(82)

相冊

收藏夾(40)

我的連接

CSDN-中國最大的IT技術社區
編程中國
博客園
長大在線
長江大學
我的博客地圖
武漢公交網
中華上下五千年

搜索

積分與排名

積分 - 490980
排名 - 41

閱讀排行榜

不確定的有窮自動機N的確定化

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

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

　　請你注意這個結論：DFA是NFA的特例
　　對每個NFA N一定存在一個DFA M，使得L(M)=L(N)。對每個NFA N存在著與之等價的DFA M。與某一NFA等價的DFA不唯一。
　　在有窮自動機的理論里，有這樣的定理：設L為一個由不確定的有窮自動機接受的集合，則存在一個接受L的確定的有窮自動機。我們不對定理進行證明，只介紹一種算法（這種算法稱為子集法），將NFA轉換成接受同樣的語言的DFA。
　　為什麼對DFA如此親睞呢？因為它的行為很容易用程序來模擬。
　　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的矩陣表示中可以看出，表項通常是一個狀態的集合，而在DFA的矩陣表示中，表項是一個狀態，NFA到相應的DFA的構造的基本想法是該DFA的每一個狀態對應NFA的一組狀態。該DFA使用它的狀態去記錄在NFA讀入一個輸入符號后可能達到的所有狀態。也就是說，在讀入輸入符號串a₁a₂…a_n之后，該DFA處在這樣一個狀態，該狀態表示這個NFA的狀態的一個子集T，T是從NFA的開始狀態沿著某個標記為a₁a₂…a_n的路徑可以到達的那些狀態。
　　為介紹算法首先定義對狀態集合I的幾個有關運算：
　　1. 狀態集合I的ε-閉包，表示為ε-closure(I)，定義為一狀態集，是狀態集I中的任何狀態S經任意條ε弧而能到達的狀態的集合。
　　回顧在前面章節對轉換函數的擴充：如輸入字符是空串，則自動機仍停留在原來的狀態上，顯然，狀態集合I的任何狀態S都屬于ε-closure(I)。
　　2. 狀態集合I的a弧轉換，表示為move(I,a)，定義為狀態集合J，其中J是所有那些可從I中的某一狀態經過一條a弧而到達的狀態的全體。
　　我們使用圖4.4的NFA N的狀態集合來理解上述兩個運算。

圖 4.4 NFA N

　　ε-closure(0)=｛0，1，2，4，7｝
　　即｛0，1，2，4，7｝中的任一狀態都是從狀態0經任意條ε弧可到達的狀態，令｛0，1，2，4，7｝=A，則 move(A,a)=｛3，8｝，因為在狀態0，1，2，4和7中，只有狀態2和7有a弧射出，分別到達狀態3和8。
　　而ε-closure(｛3，8｝)=｛1，2，3，4，6，7，8｝。

　　再看一個例子，對下圖所示NFA的狀態集合I的運算

圖 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確定化算法：假設NFA N=(K, ∑,f,K₀,K_t)按如下辦法構造一個DFA M=(S, ∑,d,S₀,S_t)，使得L(M)=L(N)：

　　① M的狀態集S由K的一些子集組成（k的子集構造算法見下頁）。用[S₁ S₂... S_j]表示S的元素，其中S₁, S₂,,... S_j是K的狀態。并且約定，狀態S₁, S₂,,... S_j是按某種規則排列的，即對于子集{S₁, S₂}={ S₂, S₁,}來說，S的狀態就是[S₁ S₂]；
　　② M和N的輸入字母表是相同的，即是∑；
　　③ 轉換函數是這樣定義的：
　　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的開始狀態；
　　⑤ S_t={[S_i S_k... S_e]，其中[S_i S_k... S_e]∈S且{S_i , S_k,,... S_e}∩K_t≠φ}

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

例 3.3 應用左面的算法對圖4.4的NFA N構造子集，步驟如下：

　　① 首先計算ε-closure(0)，令T₀=ε-closure(0)={0，1，2，4，7}，T₀未被標記，它現在是子集族C的唯一成員。
　　② 標記T₀；令T₁=ε-closure(move(T₀,a))={1，2，3，4，6，7，8}，將T₁加入C中，T₁未被標記。
　　令T₂=ε-closure(move (T,b))={1，2，4，5，6，7}，將T₂加入C中，它未被標記。
　　③ 標記T₁；計算ε-closure(move(T₁,a))，結果為{1，2，3，4，6，7，8}，即T₁，T₁已在C中。
　　計算ε-closure(move(T₁,b))，結果為{1，2，4，5，6，7，9}，令其為T₃，T₃加至C中，它未被標記。
　　④ 標記T₂，計算ε-closure(move(T₂,a))，結果為{1，2，3，4，6，7，8}，即T₁，T₁已在C中。
　　計算ε-closure(move(T₂,b))，結果為{1，2，4，5，6，7}，即T₂，T₂已在C中。
　　⑤ 標記T₃，計算ε-closure(move(T₃,a))，結果為{1，2，3，4，6，7，8}，即T₁。
　　計算ε-closure(move(T₃,b))，結果為{1，2，4，5，6，7，10}，令其為T₄，加入C中，T₄未被標記。
　　⑦ 標記T₄，計算ε-closure(move(T₄,a))，結果為{1，2，3，4，6，7，8}，即T₁
　　計算ε-closure(move(T₄,b))結果為{1，2，4，5，6，7}，即T₂。
　　至此，算法終止共構造了五個子集：
　　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構造的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₄]重新命名，以利于書寫，或用A，B，C，D，E或用0，1，2，3，4分別表示。若采用后者，該DFA M的狀態轉換圖如圖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

確定化后的自動機：

posted on 2007-04-03 22:20 譚文政閱讀(1874) 評論(1) 編輯收藏引用所屬分類: 基礎知識

只有注冊用戶登錄后才能發表評論。


相關文章: Win XP系統任務欄實用技巧總集 [轉]電子書籍制作工具軟件大全 WAV轉MP3格式最簡單的方法 C#Windows控件的焦點事件順序 C# 怎么顯示中文格式的日期、星期幾 [轉] 網頁設計者值得一去的地方！ Word表格及Excel中斜線表頭的繪制方法。 [轉] 深入剖析XP的BOOT.INI 什么是uri和url? 存儲類說明符：auto,register, extern mutable 和static

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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