语法幺半群——代数视角

上级：regular-equivalences

正则性可以完全用代数来刻画：一个语言是正则的，当且仅当有某个有限的代数对象能识别它。

幺半群的识别

一个幺半群 M（带有结合乘法与单位元的集合）识别 L ⊆ Σ*，是指存在一个同态 h : Σ* → M 和一个子集 P ⊆ M，使得 L = h⁻¹(P)。（Σ* 在拼接运算下就是自由幺半群。）

正则 = 被某个有限幺半群识别

L 是正则的，当且仅当它被某个有限幺半群识别。其中最小的那个就是语法幺半群（即最小 DFA 的转移幺半群，也是按语法同余作商后的商幺半群——语法同余是 Myhill–Nerode 关系的双边加细）。

为什么值得引入代数

幺半群的结构能分辨出自动机/正则表达式看不清楚的子族：

• Schützenberger（1965）： 一个语言是无星号的（star-free，即不用 *、只用补运算就能定义）当且仅当其语法幺半群是非周期的（内部不含非平凡的群）。
• McNaughton–Papert： 无星号 = 一阶逻辑可定义（即 MSO 的一阶片段）。

于是一个代数性质（非周期性）= 一个逻辑性质（一阶可定义）= 一个表达式性质（无星号）。这就是Eilenberg 的簇理论（variety theory）：语言族与有限幺半群族一一对应。这种一致性一路贯穿到底。