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