將正規表示式(Regular Expression)轉化成NFA之演算法.
輸入:定義於文字集(N T)上之正規表示式R.
輸出:壹個可以接受正規表示式R所定義之語言的NFA.
(1)對 所建立的NFA.
(2)對終端符號中a所建立的NFA為
每次需要壹個新的狀態(State)時,則給此新的狀態壹個新的編號,則不會有兩個狀能具有相同的編號.
Regular Expression NFA(cont'd)
Regular Expression NFA(cont'd)
(3)利用上述兩種基本正規表示式(Basic Regular Expression)的NFA建構法,則可用此兩者將復合正規表示式(Compound Regular Expression) 建構成NFA.根據下述的轉換規則便可順利的將正規表示式R建立成壹個完整的NFA.
首先,必須立壹個初始狀態(Initial State)Si及壹個終止狀態(Final State) Sf.
若是有R1│ R2這類型的復合正規表示式,則所建構的NFA如下:
Regular Expression NFA(cont'd)
若是有R1 R2這類型的復合正規表示式,則所建構的NFA如下:
Regular Expression NFA(cont'd)
若是有R1*這類型的復合正規表示式,則所建構的NFA如下:
Regular Expression NFA(cont'd)
例:將正規表示式R=(0│1)*01轉換成NFA.
首先分解正規表示式R為基本成分如下:依據上圖之架構分別求其基本NFA(Primitive NFA)與復合NFA(Compound NFA).
Regular Expression NFA(cont'd)
(1)對第壹個基成分(Primitive Component) R1,即對第壹個終端符號0所建構之基本NFA如下:
(2)同理,對R2所建構之基本NFA為:
Regular Expression NFA(cont'd)
(3)對R3= R1│ R2所建構之復合NFA如下:
(4)因為R4=(R3),所以R4之NFA與R3之NFA完全相同.
Regular Expression NFA(cont'd)
(5)對R5= R4*所建構之復合NFA如下:
Regular Expression NFA(cont'd)
(6)對R6=0所建構之基本NFA如下:
:取用狀態7'是便於稍後合並時無需再修改其他狀態之值.
Regular Expression NFA(cont'd)
(7) R7= R5 R6所建構之基本NFA如下:
:狀態7與狀態7'合並成狀態7.
Regular Expression NFA(cont'd)
(8)重上述之步驟,建構R9=(0│1)*01之NFA如下:
NFA DFA
壹般Input Symbol含有 (空字串)者
Step 1:壹個名為N之NFA欲化為名為D之DFA, D之初始狀態(initial state)是包含初狀態s0之集合,故將此state s0加入 -CLOSURE(s0)中,從s0可經由input symbol為 而到達之state均加入此 -CLOSURE(s0)中,此集合即為此DFA之initial state,設其為marked state .
Step 2: 對已marked state中元素,對每壹input symbol a( ) si marked state,若f(si, a)=sj,將所有成集合T而 -CLOSURE(T),若不等於已有的state,則設為unmarked state.
Step 3:尋找下壹個unmarked state,設其為marked stated,重復step ,直到無unmarked state為止.
NFA DFA
NFA DFA
Step 4: 由上述步驟可求得壹個Transition Table,若其含原NFA之initial state(or finial state),則此state就是initial state(or finial state) .
Step 5:依Transition Table求Transition diagram即為所求.
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
由NFA轉換所得之DFA,其中的某些態可以再合並成為壹個狀態,至於如何將DFA之狀態數最小化(Minimize)其處理方式有下述三個步驟:
步驟壹:將DFA中所有狀態所形成之狀態群(Group)G分割成終止狀態群F與非終止狀態群(G-F).
步驟二:藉由下述之分裂程序(Procedure SPLIT)對所有的狀態群做分裂(Split)處理.任壹狀態群若因分裂程序處理而產生狀態群分裂,則繼續對該分裂之獎態群做分裂處理,直至所有的狀態群皆無法再分裂為止.
DFA 最小化
DFA 最小化(cont'd)
步驟三:令每個狀態群為壹個新的狀態(State).
步驟四:刪除所有的死亡狀態(Dead States);即該狀態非初始狀態,而且無法自其他狀態到達之狀態.
DFA 最小化(cont'd)
Procedure SPLIT
begin
for each group G of P do
begin
partition G into subgroups such that two states s and t of G are
in the same subgroup if and only for all input symbol a, states s
and t have transitions to states in the same group of P;
replace all subgroups that formed in P;
end
end
DFA 最小化(cont'd)
Example
DFA 最小化(cont'd)
DFA 最小化(cont'd)
步驟壹:將狀態A,B,C,D,E分割成非終止狀態群{A,B,C,D}與終止狀態群.
步驟二:由於終止狀態群僅含有壹個狀態E,故無須再分裂.狀態{A,B,C,D}經分裂程序處理,得知狀態A,B,C,D對輸入符號0皆轉移(Transite)至狀態B(屬於同壹狀態群{A,B,C,D}中).但對於輸入符號1而言,狀態群{A,B,C,D}中僅有狀態D會轉移至狀態群,而狀態A,B,C則均會轉移至狀態群{C,D}中,故將狀態群{A,B,C,D}分裂成{A,B,C}與兩個狀能群.由於狀態群僅含有壹個狀態D,故無須再分裂.再對狀態群{A,B,C}做分裂處理,對於輸入符號0狀態A,B,C均轉移至狀態B,但對輸入符號1,僅有狀態B會轉移至狀態D(即狀態群中),故再將狀態群{A,B,C}分裂成{A,C},.至此,無法再分裂了.
DFA 最小化(cont'd)
步驟三:令每壹個狀態群為壹新的狀態.
{A,C}=S1
令{A,C}=S1
= S2
= S3
= S4
步驟四:無任何死亡狀態,故不須刪除任何壹個狀態.
由上可得到的轉移表(Transition Table)為
最後,求得最小狀態數之DFA為
FA Regular Grammar
將有限自動機(Finite Automata)轉成正規文法(Regular Grammar)之方法:
(1)若狀態A對於輸入的終端符號a會到達狀能B,而且狀態B並非終止狀態(Final State),則其正規文法為A aB.
(2)若狀態A對於輸入的終端符號a會到達狀態B,而且狀態(Final State),則其正規文法A a, A aB.
(3)若狀態A對於輸入的終端符號a會到達狀態A本身,而且狀態A既是初始狀態(Initial State)亦是終止狀態,則其正規文法為A ,A a與A aA.
例:
則其正規文法為G=,N={S,A,B,C},T={0,1},P={
S , A 0C, B 0C, C 0C,
S 0, A 1C, B 1B, C 1C}
S 0A, B 1,
S 1,
S 1B,
根據上面之文法,可求得相對應之語言為L(G)={0,1*}.