有限狀態機（finite-state machine）

想像地鐵的旋轉柵門。此刻它是上鎖的。你投入一枚硬幣，它就解鎖；你走過去，它又重新上鎖。柵門不記得昨天有多少人走過，也不記得它一共收過幾枚硬幣。在任一瞬間，它所知道的一切都濃縮成一個詞：上鎖或解鎖。這個唯一的詞就是它的狀態（state），而一部全部記憶就只有這樣一個狀態、且狀態取自一張固定有限清單的機器，就叫做有限狀態機。

更精確地說，有限狀態機由左到右、一次讀一個符號地讀入輸入；每讀完一個符號，它就恰好處於有限多個狀態之一。從一個符號帶到下一個符號的，只有「現在在哪個狀態」這件事；沒有便條紙、沒有計數器、旁邊也沒有額外的儲存空間。一條規則（轉移）告訴你：在目前狀態下讀到剛才那個符號，應該移到哪個狀態。紅綠燈（綠轉黃、黃轉紅、紅轉綠）以及記錄已投入多少錢的自動販賣機，都是日常生活中的有限狀態機。

「有限狀態」這個詞既是核心，也是它誠實的限制。因為狀態只有有限多個，無論輸入變得多長，機器能記住的資訊量都是有界的。它能記住上一個看到的符號、目前計數是奇是偶、或它正在等待三枚硬幣中的哪一枚，卻無法記住一個任意大的累加總和。正是這道界線使有限狀態機簡單到可以被完整分析，也正是它為何無法（例如）檢查括號是否在任意深度都成對配平。