正規表示式

數學敘述

typed AST只允許empty-language、epsilon、alphabet symbol、union、ordered concatenation與star；每個symbol須屬明示alphabet。語義遞迴定義language，star的bounded enumeration以fixed-point closure處理epsilon cycle並extensional dedup。word membership必須完整決定，不因某個不足的bound沒列出就判false。Union canonicalize permutation/idempotence，concatenation保留次序。empty language與{epsilon}、regex與shell wildcard分開；長度≤N語言相同不證全語言等價。

代表公式（精確 TeX）

R(A,w)=b

成立條件

• alphabet finite unique，word是alphabet symbols的有限序列。
• AST node types與arity完整驗證。
• bounded language只標示長度≤N，不冒充unbounded equivalence。

符號作用域

• R — 正規表示式語義算子
• A — 有限alphabet
• w — 有限word
• b — 成員布林值

直觀、定義與常見誤解

typed AST與alphabet資格先行。

bounded star closure處理epsilon與去重。

membership completeness和bounded-equivalence邊界分開。

把empty language當epsilon、把shell wildcard當Kleene star，或以有限bound宣稱regex等價。

已採用的推導導讀

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

前置知識

• 正規語言 — 語義codomain。
• 集合 — language union。
• 數列 — word與concatenation。
• 數學歸納法 — AST與star語義遞迴。

驗證界線

bounded enumeration只證指定長度切片。

not_formalized

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

下一個義務

加入regex-to-NFA construction與equivalence decision。

同源結構化資料

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