# 正規表示式

正規表示式由empty language、epsilon、alphabet symbols、union、concatenation與Kleene star遞迴建構語言。

mko-regular-expression · definition · v0.10.0



## 數學敘述

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等價。





## 已採用的推導導讀

[含epsilon的star閉包與完整長度切片](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-regular-expression-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [正規語言](https://ocme.evemisslab.com/zh-Hant/mko/mko-regular-language/) — 語義codomain。
- [集合](https://ocme.evemisslab.com/zh-Hant/mko/mko-set/) — language union。
- [數列](https://ocme.evemisslab.com/zh-Hant/mko/mko-sequence/) — word與concatenation。
- [數學歸納法](https://ocme.evemisslab.com/zh-Hant/mko/mko-mathematical-induction/) — AST與star語義遞迴。





## 驗證界線

bounded enumeration只證指定長度切片。

not_formalized

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





## 下一個義務

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





## 同源結構化資料

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

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