[CS] 確定有限狀態自動機 DFA (deterministic finite automaton)

定義

DFA(deterministic finite automaton, 確定有限狀態自動機)屬於FSM(finite-state machine, 有限狀態機)的一種分類，根據Wikipedia的說明:

在計算理論中，確定有限狀態自動機或確定有限自動機（英語：deterministic finite automaton, DFA）是一個能實現狀態轉移的自動機。 對於一個給定的屬於該自動機的狀態和一個屬於該自動機字母表的字元，它都能根據事先給定的轉移函式轉移到下一個狀態（這個狀態可以是先前那個狀態）。

啊…看不懂

我不想套用學術表示式來說明DFA是啥，基本上，自動機可以用圖表來表示，就用個簡單的例子(取自Wikipedia)來說：

這個圖表裡面，有一些元素：

• S1, S2這兩個以圓圈表示的，就是狀態(State)
• S1以雙重圓圈表示，這就是結束狀態．結束狀態可以有複數個．
• 箭頭表示流程，箭頭旁邊的文字是它的字母，也就是當輸入是這個字母時，要轉移到哪一個狀態． 譬如說，S1有個箭頭指向S2，旁邊是0這個字母，表示當輸入為0的時候，S1會轉移到S2 箭頭可以指向自己，譬如S1和S2都有指向自己本身的箭頭，箭頭的字母為1，也就是說當輸入為1的時候，轉移向自己，相當於沒有變化狀態
• 沒有起始狀態的箭頭，表示為起始輸入，它所指向的狀態就是起始狀態．整個流程就是從這個起始狀態開始，在上面的例子裡面，S1就是起始狀態．

給予這個自動機一個輸入字串，從起始狀態開始，一個字元一個字元的根據箭頭和它的表示字元來移動，如果最後移動到一個結束狀態，我們就說自動機接受這個字串，反之就是自動機拒絕這個字串．

如果還是不了解，這裡有個解釋FSM的影片，我覺得說明得還不錯：

應用

DFA在Programming/Coding的最大應用就是正規表示式，或稱規則運算式（Regular Expression, RegEx)

這個要說起來就比較費工夫啦，所以先拿個網路上的影片來擋一下，請自行觀看，等有機會我再來寫篇文章解釋：