確定型有限自動機（deterministic finite automaton）

確定型有限自動機，簡稱 DFA，是計算理論中最簡單的真實機器，也是你接觸的第一部真正的自動機。再想想旋轉柵門或自動販賣機：它一次讀一個符號，全部記憶就只有一個狀態，而對任何「狀態加符號」的組合，它接下來該做的事都恰好只有一件。「確定型（deterministic）」這個詞保證永遠沒有選擇、沒有模稜兩可：給定你在哪裡、剛讀到什麼，下一個狀態就被完全決定了。

DFA 的執行方式如下。它從一個指定的起始狀態開始，由左到右讀入輸入字串；每讀一個符號，就沿著「目前狀態」與「該符號」對應的那條唯一箭頭走到新狀態。當輸入讀完時，它檢視自己最後停在哪個狀態。如果那個最終狀態屬於被標記的接受狀態，DFA 就接受這個字串；否則就拒絕。所以 DFA 本質上是個是／否的判定器：其字母表上的每個字串都恰好得到一個裁決。

DFA 的重要性遠遠超出玩具範圍。它是編譯器詞法分析階段（辨識關鍵字與數字）背後的引擎，是搜尋取代與許多正規表示式比對器背後的引擎，也是通訊協定與硬體控制器背後的引擎。它同時是探問「有限記憶能做什麼、不能做什麼」最乾淨的模型，正因如此，一整套理論——正規語言、幫浦引理、最小化——都建立在它之上。