確定有限自動機
DFA (Deterministic Finite Automata)
DFA定義
DFA就是一個計算機，能計算有限狀態下，每次輸入確定轉移到哪個唯一的狀態．
確定(Deterministic)
隨時都能確定在哪個狀態下
有限(Finite)
狀態是有限的
自動機(Automata)
計算機的意思
DFA數學定義
A deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q0, F), consisting of
a finite set of states (Q) a finite set of input symbols called the alphabet (Σ) a transition function (δ : Q × Σ → Q) an initial or start state (q0 ∈ Q) a set of accept states (F ⊆ Q) Let w = a1a2 ... an be a string over the alphabet Σ. The automaton M accepts the string w if a sequence of states, r0,r1, ..., rn, exists in Q with the following conditions:
r0 = q0 ri+1 = δ(ri, ai+1), for i = 0, ..., n−1 rn ∈ F.
狀態轉移函數
δ(q,w) -> q' 狀態q之下輸入w得到q'的狀態
狀態圖
狀態轉移列表
例如
| Input/State | 0 | 1 | |
|---|---|---|---|
| S1 | S2 | S1 | |
| S2 | S1 | S2 |
其實{0,1}就是輸入，{S1,S2}就是non-terminal symbol．這個狀態轉移列表就是文法(Grammar)的列表啦，自動機就照著這個列表決定輸出的狀態，也就是輸出語言的文法，這個文法的序列就是你執行語言的行動(Action)，那>自動機其實就是把輸入翻譯成一連串的Action，這不就是計算機嗎？另外終結狀態，其實就是terminal symbol，他本身就帶有語意，也就是關鍵字或常數，不需要再推導了．