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
春秋十二月 阅读(61)
评论(0) 编辑 收藏 引用 所属分类:
Compiler