# 正規語言

正規語言是存在一個完整DFA可辨識其全部字串的語言。

mko-regular-language · definition · v0.10.0



## 數學敘述

DFA certificate須涵蓋宣告alphabet上的任意有限word。mod-count/parity語言以state invariant對任意字長證明；有限語言可用prefix-trie DFA構造。有限測試字不足以證regularity或language equivalence。





## 代表公式（精確 TeX）

R(L)





## 成立條件


- 有限alphabet與完整DFA總轉移。
- 本輪不引入regex、NFA、epsilon transition、minimization或pumping lemma。





## 符號作用域


- R — 正規語言證書
- L — 字串集合





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

存在完整DFA是全語言證書。

parity/mod-count用任意prefix invariant。

有限語言可構造DFA；有限測試通過不足。

用少數字串測試就宣稱regular或兩語言相等。





## 已採用的推導導讀

[任意字長的parity invariant](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-regular-language-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [確定有限自動機](https://ocme.evemisslab.com/zh-Hant/mko/mko-finite-automaton/) — DFA辨識證書。
- [集合](https://ocme.evemisslab.com/zh-Hant/mko/mko-set/) — language為word集合。
- [數列](https://ocme.evemisslab.com/zh-Hant/mko/mko-sequence/) — word是有限符號序列。
- [決定問題](https://ocme.evemisslab.com/zh-Hant/mko/mko-decision-problem/) — membership接受／拒絕。





## 驗證界線

只處理DFA與明示invariant／有限語言構造，不外推其他模型。

not_formalized

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





## 下一個義務

加入NFA、regular expression與closure construction。





## 同源結構化資料

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

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