又來了

一般的 finite automata 是 deterministic finite automata（DFA），而有種 non-deterministic finite automata（NFA）能自己在過程中分裂成多個 DFA，所以顯然 DFA 是 NFA 的特化；然而經過證明，任何 NFA 都能轉換為計算能力等價的 DFA ─ 因此 NFA 等價於 DFA。又是「一即全體」的情形（cf. the MVT family）。下一節是 regular expressions，先整理一下到目前所學：

• 定義：DFA
• 定義：NFA
• 定義：DFA 認得（recognizes）某個字串
• 定義：NFA 認得（recognizes）某個字串
• 定理：NFA ==> DFA
• 定義：regular language
• 每部 DFA 都認得恰好一種（one and only one）language
• 作用於 languages 的三種操作：聯集（union）、串接（concatenation）、星號（star）
• 定理：三種操作對於 regular languages 的封閉性

雖然寫得很有趣，這本書和所有類似書籍一樣（不是它們的錯），不太能明確揭示「所呈現理論」在整體科學邏輯網內的角色，這有待自己思考。

--
再搭配 Visual Automata Simulator，automata 真的很好玩 XD。