1. NFA到DFA:設(shè)NFA的狀態(tài)數(shù)為n,根據(jù)子集構(gòu)造法,則至多有2^n個狀態(tài)轉(zhuǎn)移,對每個狀態(tài)轉(zhuǎn)移,其狀態(tài)分量至多有n個狀態(tài),每個狀態(tài)計算它的可達狀態(tài)集合耗時為O(n^2),另可達狀態(tài)集合的并耗時為O(n^2),故一個轉(zhuǎn)移耗時為n*O(n^2)=O(n^3),則所有轉(zhuǎn)移總耗時為O(n^3*2^n)。由于實際產(chǎn)生的狀態(tài)數(shù)遠小于2^n(通常為n),因此耗時為O(n^3*s),s為DFA實際具有的狀態(tài)數(shù)
2. DFA到NFA:轉(zhuǎn)化方法是修改轉(zhuǎn)移表,對每個狀態(tài)轉(zhuǎn)移的目標(biāo)狀態(tài)加上集合括號(因NFA對特定輸入可能有多個目標(biāo)狀態(tài),故為集合),若轉(zhuǎn)為£-DFA,則還需對每個狀態(tài)增加對£的轉(zhuǎn)移為空集。該方法耗時為O(n),n為DFA的狀態(tài)數(shù)
3. DFA到正則表達式:設(shè)DFA狀態(tài)數(shù)為n,根據(jù)遞推公式R(i,j,k)=R(i,j,k-1)+R(i,k,k-1)R(k,k,k-1)^*R(k,j,k-1)(1<=i<=j<=n,0<=k<=n)來逐步構(gòu)造表達式,最終的表達式就是所有R(1,j,n)的并,其中j為可接受狀態(tài)。該過程會產(chǎn)生總共n^3+n^2個表達式,每次k遞增導(dǎo)致表達式長度增為4倍,故總耗時為O(n^3*4^n)。另一種更快的方法是消除所有除初始和接受狀態(tài)外的中間狀態(tài),每次消除一個,就合并其前驅(qū)經(jīng)過它到其后繼的正則表達式和前驅(qū)直接到后繼的正則表達式,因前驅(qū)或后繼至多n-2個,則共有(n-2)^2個前驅(qū)到后繼的直通邊,且中間狀態(tài)至多n-2個,故耗時為O(n^3);最后合并各接受狀態(tài)的正則表達式,因接受狀態(tài)至多n-1個,故耗時為O(n)。故總耗時為O(n^3)
4. 正則表達式到£-NFA:作詞法分析,對每個終結(jié)符號構(gòu)建狀態(tài)結(jié)點及轉(zhuǎn)移邊,即子£-NFA,特定符號對應(yīng)用并、連接、閉包、結(jié)合之一聯(lián)合已構(gòu)建的子£-NFA,耗時為O(n),n為正則表達式的長度
posted on 2023-09-06 23:42
春秋十二月 閱讀(94)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler