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