正規語言

數學敘述

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或兩語言相等。

已採用的推導導讀

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

前置知識

• 確定有限自動機 — DFA辨識證書。
• 集合 — language為word集合。
• 數列 — word是有限符號序列。
• 決定問題 — membership接受／拒絕。

驗證界線

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

not_formalized

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

下一個義務

加入NFA、regular expression與closure construction。

同源結構化資料

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