確定有限自動機

數學敘述

完整核Q×Σ每一輸入恰有一個合法輸出；依序追蹤完整有限word。空字接受恰當初始狀態為接受狀態。一組有限trace不證語言等價或regularity。

代表公式（精確 TeX）

D(Q)

成立條件

• 有限非空state set與有限非空alphabet，轉移表完整且決定。
• 無epsilon transition，不引入NFA語義。

符號作用域

• D — DFA紀錄
• Q — 有限狀態集

直觀、定義與常見誤解

完整轉移表保證deterministic與total。

從唯一初始狀態逐符號更新。

空字不走轉移；有限trace不證兩DFA語言等價。

漏轉移、把NFA多分支或epsilon transition混入DFA，或由少數測試字宣稱語言等價。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 抽象計算模型 — DFA為有限計算模型。
• 離散時間動力系統 — 轉移迭代。
• 函數映射 — 轉移須為總函數。
• 集合 — 狀態、字母與接受集。
• 數列 — word為有限有序符號列。

驗證界線

只處理完整DFA與有限word trace；不宣稱一般regular language結果。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

加入正規語言、NFA與等價構造。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。