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