RE(Regular Expression)到最小DFA(Deterministic Finite Automaton)的轉(zhuǎn)換是構(gòu)建正則表達(dá)式引擎的基礎(chǔ),并且也是構(gòu)建詞法分析器的基礎(chǔ).
RE
RE描述了一個定義在某個字母表Σ上的字符串集合L,并且空字符串ε也屬于L集合.形式化的定義并不好理解,但是相對其他非形式化的定義來說更加簡潔和準(zhǔn)確.這里的正則表達(dá)式和平常所用的處理字符串的正則表達(dá)式是同一個,但是這里更加簡單.這里的RE只有三個基本的操作:
(1)選擇 取并集.符號:|. 比如兩個字符串集合R和S的選擇操作,記作R|S.
(2)連接 字符串之間的拼接.兩個字符串集合R和S的連接為RS.
(3)閉包 符號:* 字符串集合R的閉包R*是指把R與自身連接零次或者多次形成的所有集合的并集.
??由這幾個簡單的操作可以得到我們平常接觸的正則表達(dá)式的所有擴(kuò)展.
有限狀態(tài)自動機(jī)(Finite Automaton,FA)
我說的時候喜歡加上狀態(tài)兩個字,因?yàn)镕A的關(guān)鍵動作就是狀態(tài)間的轉(zhuǎn)移.FA有一個狀態(tài)集S,對于每一個輸入都會讓FA的狀態(tài)進(jìn)行轉(zhuǎn)移.如果能夠從起始狀態(tài)轉(zhuǎn)移到接受狀態(tài),那么輸入序列就被識別了.不存在空字符串ε的狀態(tài)轉(zhuǎn)移.
??非確定性有限狀態(tài)自動機(jī)(Non-deterministic Finite Automaton,NFA).對于同一輸入轉(zhuǎn)移到多個不同的狀態(tài)或者存在空字符串ε的狀態(tài)轉(zhuǎn)移的FA.
??確定性有限狀態(tài)自動機(jī)(Deterministic Finite Automaton,DFA).對于任何確定的輸入都只有唯一確定的轉(zhuǎn)移且不存在空字符串ε的狀態(tài)轉(zhuǎn)移的FA.
從正則表達(dá)式到NFA
上面描述的RE的基本操作的簡單NFA:
只要有了這三個RE基本操作的NFA,我們就能對任何組合得來的RE求出對應(yīng)的NFA.
NFA到DFA
NFA到DFA 是對NFA的簡化過程.
??NFA到DFA的子集構(gòu)造算法(The Subset Construction):從將初始狀態(tài)劃分為一個初始狀態(tài)子集開始,構(gòu)造狀態(tài)子集(經(jīng)過零個或多個空字符串ε轉(zhuǎn)移到的狀態(tài)和已在子集中的狀態(tài)都是構(gòu)造的新的狀態(tài)子集),存在c屬于字母表Σ,經(jīng)過一個c的轉(zhuǎn)移(必須有c的轉(zhuǎn)移),能夠使得從狀態(tài)子集ni轉(zhuǎn)移到狀態(tài)子集nj,則在DFA中有在c的輸入下從狀態(tài)子集ni轉(zhuǎn)移到狀態(tài)子集nj的轉(zhuǎn)移.最后不再有新的狀態(tài)子集出現(xiàn).根據(jù)狀態(tài)子集的轉(zhuǎn)移依次構(gòu)造DFA.
DFA到最小DFA
最小化DFA用到的是等價狀態(tài)集合的劃分來構(gòu)建.一開始只有兩個狀態(tài)集,一個接受狀態(tài)集合,一個非接受狀態(tài)集合.對于每一個狀態(tài)集合Sp,如果存在c屬于字母表Σ,使得Sp中的狀態(tài)轉(zhuǎn)移到不同的狀態(tài)集合(包括沒有轉(zhuǎn)移的空狀態(tài)集合),則拆分Sp,使得拆分后的狀態(tài)集合中的每一個狀態(tài)不可能轉(zhuǎn)移到不同的狀態(tài)集合.其中狀態(tài)集合之間的轉(zhuǎn)移構(gòu)成最小化DFA中的轉(zhuǎn)移.
