2021-04-11 子集構(gòu)造法有效性證明

本文主要介紹一下編譯原理中的子集構(gòu)造法的數(shù)學(xué)依據(jù)。
龍書(shū)中并沒(méi)有給出證明，我們?cè)谶@里補(bǔ)上。
網(wǎng)上雖然有一些證明，但大多數(shù)不是很細(xì)，這里給出一個(gè)詳細(xì)的證明

NFA的形式化定義如下：
NFA=(K,\sigma,f,S,Z) 為一個(gè)5元組
其中K是所有狀態(tài)的集合，\sigma是符號(hào)集合，
f是一個(gè)映射:f:K\times \sigma -> 2^K (其中2^K表示K的所有子集的集合,對(duì)于該映射的像為空集的情形，把對(duì)應(yīng)原像從定義域中排除，從而使得該映射的定義域?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=K%5Ctimes%20%5Csigma" alt="K\times \sigma" mathimg="1">的子集，這一點(diǎn)后文中保持一致并且不再說(shuō)明)
S為初始狀態(tài)集合S\subset K
Z是終止?fàn)顟B(tài)集合 Z\subset K

DFA為NFA的特例，滿足以下兩個(gè)額外條件:
1,S只包含一個(gè)元素
2, f的任意象 都最多只包含一個(gè)元素

以上形式化定義十分抽象，但其實(shí)NFA只不過(guò)表達(dá)了一個(gè)無(wú)重邊的有向圖,K對(duì)應(yīng)圖的節(jié)點(diǎn)，\sigma對(duì)應(yīng)圖的邊上的符號(hào)，若f(k,c) = T 則表示，k到T中每個(gè)元素都有一條有向邊，且這些邊上的符號(hào)為c, S和Z僅僅是K的特殊子集

子集構(gòu)造法主要是把一個(gè)NFA轉(zhuǎn)化為一個(gè)DFA，為了給出其形式化描述，我們先給出以下定義:
1，給定NFA=(K,\sigma,f,S,Z)
給定任意子集L\subset K,以及任意一個(gè)符號(hào)c\in \sigma
令 f(L,c):= \cup f(x,c) 任意x \in L

待構(gòu)建的DFA記為: DFA = (K',\sigma',f',S',Z')
則有K'\subset 2^K , \sigma' = \sigma ,
f' : K' \times \sigma' \rightarrow 2^{K'}
注意，根據(jù)DFA的定義，其象最多只能包含一個(gè)元素，對(duì)于只包含一個(gè)元素的集合，我們這個(gè)元素替代，而對(duì)于不包含任何元素的集合，我們可以把其原像從定義域中排除；則上式可以簡(jiǎn)寫(xiě)為:
f' : K' \times \sigma' \rightarrow K' 但是這個(gè)映射的定義域并非K'\times \sigma'而是其 子集。

簡(jiǎn)單來(lái)說(shuō)，DFA的狀態(tài)是 原始NFA的狀態(tài)集合，其映射f'把某個(gè)狀態(tài) s\in K'和 某個(gè)符號(hào)c\in \sigma'映射為唯一的狀態(tài) s'\in K' ，但是有些映射的像為空（這些映射的原像將被我們從定義域 K'\times \sigma'中排除）

有了以上鋪墊，我們用偽代碼的形式，形式化的描述子集構(gòu)造法:

0,初始5元組中所有集合為空集,f'的定義域?yàn)榭占?br> 1取定s' = S并將其添加到 K',S',并令s'為未標(biāo)定態(tài)
2，
\quad while(K'中存在未標(biāo)定的元素s)\{
\quad \quad 標(biāo)定 s
\quad \quad for( c: \sigma) \{
\quad \quad t = f(s,c)（若(s,c)不在定義域，則continue）
\quad \quad if(t\notin K') t\rightarrow K' (箭頭這里表示添加的意思，同時(shí)令該t為未標(biāo)定態(tài))
\quad \quad 在f'的定義域中添加(s,c),并令 f'(s,c)=t
\quad\quad \}
\quad \}

以上算法確定了除了Z'之外的所有元素，之后我們把K'中所有包含位于Z中元素的的對(duì)象取出組成一個(gè)集合，設(shè)為Z'

至此我們按照算法完全構(gòu)建了 DFA

下面我們來(lái)做最關(guān)鍵的一步，證明以下兩點(diǎn):
1，子集構(gòu)造法生成的圖 確實(shí)滿足DFA應(yīng)該滿足的性質(zhì)
2, 該DFA和原始NFA表達(dá)相同的語(yǔ)言

證明：
1, DFA應(yīng)該滿足的性質(zhì)為:
1-1,S'只包含一個(gè)元素
1-2, f'的任意象 都最多只包含一個(gè)元素
根據(jù)我們的構(gòu)建算法，S'中只包含s'，因此1成立，且由于f是單值映射，顯然2成立

2，該DFA和原始NFA表達(dá)相同的語(yǔ)言
2-1
首先證明原始NFA的語(yǔ)言包含于DFA
我們把形如:
a_1\in f(a_0,e_0), a_2\in f(a_1,e_1),.., a_n\in f(a_{n-1},e_{n-1})
的關(guān)系簡(jiǎn)稱(chēng)為“包含鏈”,當(dāng)a_0\in S時(shí)，
對(duì)于NFA表達(dá)的語(yǔ)言中的任意一條語(yǔ)句，e_0e_1...e_{n-1}，顯然必然存在滿足上述條件的包含鏈

對(duì)于這樣一條語(yǔ)句，我們考慮DFA構(gòu)造方法,

有a_0\in S \in S'
S會(huì)被執(zhí)行一次標(biāo)定，之后對(duì)于符號(hào)e_0，將執(zhí)行
t= f(S,e_0)=\cup f(x,e_0) 任意x\in S 以及t->K'
由a_1\in f(a_0,e_0) ,a_0\in S, 推出 a_1\in t
并且將有: f'(S,e_0)= t 我們?cè)O(shè)S_1= t；

則S_1會(huì)被執(zhí)行一次標(biāo)定，之后對(duì)于符號(hào)e_1將執(zhí)行
u =f(S_1,e_1)=\cup f(x,e_1)任意x\in S_1 以及 u->K'
由a_2\in f(a_1,e_1),a_1\in S_1,推出a_2\in u
并且將有: f'(S_1,e_1) = u令 S_2=u ;

.......，最終得到:
f'(S,e_0)=S_1 ,f'(S_1,e_1)=S_2,... f'(S_{n-1},e_{n-1})=S_n
而這等價(jià)于是說(shuō):e_0e_1...e_{n-1}屬于 該DFA的語(yǔ)言。

從最初選擇NFA的語(yǔ)句的任意性，證明完畢

2-2 其次證明DFA的語(yǔ)言不會(huì)超過(guò)NFA的語(yǔ)言，
DFA表達(dá)的語(yǔ)言中任意語(yǔ)句: e_0e_1,...e_{n-1} 根據(jù)DFA映射特性，存在唯一的T_0,T_1,...T_n滿足以下條件：
1)T_0=S

T_1 = f'(T_0,e_0) ,T_2=f'(T_1,e_1),...T_n=f'(T_{n-1},e_{n-1})
我們考慮其中任意一個(gè)片段:
T_i = f'(T_{i-1},e_{i-1}) , T_{i+1}=f'(T_{i},e_{i})
根據(jù)DFA構(gòu)造算法，
T_i = f'(T_{i-1},e_{i-1}) = f(T_{i-1},e_{i-1}) =\cup f(x,e_{i-1}) 任意x \in T_{i-1}
將被執(zhí)行一次，之后Ti不會(huì)再被修改
這意味著Ti中任意元素y都，存在T_{i-1}中至少一個(gè)元素x使得 y=f(x,e_{i-1})

利用這個(gè)關(guān)系，我們不難推導(dǎo)出，存在元素:
x_0\in T_0,x_1\in T_1,...x_n\in T_{n}滿足f(x_0,e_0)=x_1,f(x_1,e_1)=x_2,...f(x_{n-1},e_{n-1})=x_{n}
結(jié)合x_0\in S
這對(duì)應(yīng)著NFA中的一條語(yǔ)句
證明完畢

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容