DFA 的一次計算（a computation of a DFA）

DFA 在某個輸入字串上的一次計算（或一次執行），是機器逐一讀過該字串的逐步實況：它一個一個讀符號時所經過的狀態序列。想像你的手指在狀態圖上行走，這次計算就是手指留下的足跡。它是單一一條路徑，因為機器是確定型的。

說得詳細些，在輸入 w = a1 a2 ... an 上，這次計算是一串狀態 r0, r1, ..., rn，其中 r0 = q0（你從起始狀態開始），而每個下一狀態都遵循規則 ri = δ(ri-1, ai)（讀第 i 個符號，走它指定的那一支箭頭）。對 n 個符號的字串，會有 n+1 個狀態，因為你記下了「讀任何東西之前」以及「讀完 n 個符號中每一個之後」的所在。最終狀態 rn 就是決定裁決的那一個。

兩個特徵使 DFA 的計算格外溫馴。它是唯一的：同一部機器在同一個輸入上永遠產生同一條單一路徑，沒有要探索的分岔。它的長度恰好等於輸入：讀 n 個符號花 n 步，所以 DFA 處理任何字串所需的時間正比於其長度，且只用「記住一個狀態」所需的常數記憶量。這正是為什麼 DFA 是串流式、單趟、常數記憶辨識的模型。