Re: [討論] 想問個有點笨的問題
※ 引述《civelant (阿痕)》之銘言：
: 給一個NFA 如何將其轉為DFA?
想法很簡單, 在一個 NFA 中可以一次有多個 active state,
那你可以把所有 state 的 activity 一起看成一個單一的 state.
或者寫成數學好了:
NFA: (S, Σ, T, s0, A)
S : a finite set of states
Σ: a finite set of input symbols
T : S ╳ (Σ ∪ {ε}) → S*, a transition function
s0: a set of initial states
A : a set of accepting states
欲轉換成
DFA: (S', Σ', T', s', A')
則使得
S' = S*
Σ' = Σ
T'(X, σ): S' ╳ Σ → S' = E(∪[x in X]T(x, σ))
s' = E(s0)
A = {X in S' | X ∩ A ≠ φ}
定義 E 用來處理 ε-transition:
E(X): S' → S' = X , if ∪[x in X]T(x, ε) - X = φ
E(∪[x in X]T(x, ε) ∪ X) , else
相信看完這段之後問題應該比原本還多吧, 有問題儘量問. XD
--
その乾いた哀愁の瞳に去來するものは何か？
失ったもの 得たもの
そして廣大なネットの狹間で彼が見たものとは？
虛像と實存と記號の中に彼は今、何を想うのか？
＜バトルプログラマーシラセ＞
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.224.64
※ 編輯: Freak1033 來自: 140.109.224.64 (04/26 01:12)
推
04/26 01:34, , 1F
04/26 01:34, 1F
推
04/26 01:44, , 2F
04/26 01:44, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：