狀態轉移函數

State Transition Function

講白就是文法啦

數學律

我個人認知的狀態轉移函數計算規則

結合律

δ(q, xyz) = δ(δ(q,xy),z) = δ(δ(δ(q,x),y,z)

分配律

δ({q1,q2,q3,...qk},w) = { δ(q1,w), δ(q2,w), δ(q3,w),... ,δ(qk,w) }

NFA to ε-NFA

δ(q,w) -> δ(q,wε) δ(q,wε) = δ(δ(q,w),ε) = CL(δ(q,w)) 其中CL(A)表示從狀態A經過ε路徑可以轉換的所有狀態集合

NFA to DFA

δD({q1, q2, q3, ... qk}, A) = union(δN(qi, A)) 其中 i = 1, 2, 3 ... k

講白話就是把NFA透過輸入推導出輸出，然後再用分配律繼續推導，直到你整個集合裡面沒有新增的狀態，也就是狀態集穩定，那這個穩定（確定）的狀態集就是DFA．'