等价性：一切都在"正则"处汇合

Parent: regular-languages

正则语言是这样一个语言类：从表达式、机器、文法，一直到逻辑与代数，这些彼此独立提出的定义，最终都刻画出同一批集合。 每一个等价关系都值得单独写一篇文章。

汇合点

regex ⟺ finite automaton ⟺ right-linear grammar ⟺ finite Myhill–Nerode index ⟺ MSO-definable ⟺ recognized by a finite monoid。

各个等价关系（逐一列出）

• kleene-theorem — 正则表达式 ⟺ 有限自动机（Thompson 构造、子集构造、状态消去法 / Arden 引理）。
• myhill-nerode — 有限后缀索引 ⟺ 正则；给出唯一的最小DFA，也是证明非正则性最干净的手法。
• mso-and-automata — MSO 逻辑 = 正则（Büchi–Elgot–Trakhtenbrot 定理）；逻辑与自动机之间的桥梁。
• syntactic-monoid — 可被有限幺半群识别；代数视角（以及无星 = 非周期）。

为什么这不只是整齐，而是美

几乎没有哪个语言类拥有这么多相互独立的面孔。当一个来自逻辑的定义、一个来自代数的定义、一个来自机器的定义，全都落在同一个对象上时，你就找到了某种结构上根本性的东西——正则 = 表达式、机器、文法、逻辑、代数全部达成一致的那个不动点。 它是每个人最先学到的东西，也是最后仍然保持简单的东西。