第三型 — 正则语言（无记忆）

上级：chomsky-hierarchy

这是最底层：由除了当前状态之外没有任何记忆的机器所识别。它的特别之处在于，三种彼此独立的形式系统——以及更多其他系统——都恰好定义出同一个语言类。 每种形式系统各自成篇；这个巧合本身也值得单独记一笔。

三种形式系统

• regular-expressions —— ∅, ε, symbols 在并、连接、星号操作下封闭。
• finite-automata —— DFA / NFA：有限多个状态，没有辅助记忆。
• regular-grammar —— 右线性文法 A → aB | a。

它们彼此完全等价（Kleene 定理，加上 Myhill–Nerode 定理、MSO 逻辑、有限幺半群）——这个等价性及其构造方法本身独立成篇：regular-equivalences。

唯一的局限

泵引理（正则语言版本）

正则语言中任何足够长的词 w 都可以拆分为 w=xyz，满足 |xy|≤p、y≠ε，使得对所有 i≥0，xyⁱz 仍在该语言中。

推论：aⁿbⁿ 不是正则语言——没有记忆就不能计数，因此无法让两段匹配起来。（Myhill–Nerode 给出的证明更干净——见 regular-equivalences。）正是这个局限，促使你向上爬升到 a stack。

事实

• 封闭性： 并、连接、星号、补、交——构成一个布尔代数。
• 可判定性： 成员资格、空性、等价性——都可判定且高效。
• 用途： 词法分析器、grep、协议/状态机。