# 確定有限自動機

DFA由有限狀態集、有限字母表、總轉移函數、唯一初始狀態與接受狀態子集組成。

mko-finite-automaton · definition · v0.10.0



## 數學敘述

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





## 代表公式（精確 TeX）

D(Q)





## 成立條件


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





## 符號作用域


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





## 直觀、定義與常見誤解

完整轉移表保證deterministic與total。

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

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

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





## 已採用的推導導讀

[完整DFA的1011追蹤](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-finite-automaton-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [抽象計算模型](https://ocme.evemisslab.com/zh-Hant/mko/mko-computational-model/) — DFA為有限計算模型。
- [離散時間動力系統](https://ocme.evemisslab.com/zh-Hant/mko/mko-discrete-dynamical-system/) — 轉移迭代。
- [函數映射](https://ocme.evemisslab.com/zh-Hant/mko/mko-function-mapping/) — 轉移須為總函數。
- [集合](https://ocme.evemisslab.com/zh-Hant/mko/mko-set/) — 狀態、字母與接受集。
- [數列](https://ocme.evemisslab.com/zh-Hant/mko/mko-sequence/) — word為有限有序符號列。





## 驗證界線

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

not_formalized

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





## 下一個義務

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





## 同源結構化資料

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

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/finite-automaton.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-finite-automaton/index.md)