Myhill–Nerode 定理——后缀的代数

父级：regular-equivalences

一种通过前缀有多少种"未来"来刻画正则性的方法，也是唯一最小 DFA 的来源。

不可区分性

对于语言 L，两个字符串等价，记作 x ≡ y，当且仅当它们拥有相同的延续：对所有的 z，都有 xz∈L ⟺ yz∈L。

Myhill–Nerode

L 是正则的，当且仅当 ≡ 只有有限多个等价类，且该数目等于唯一最小 DFA 的状态数。

为什么： 这些等价类就是状态本身。一个最小 DFA 无法区分 x 和 y，除非存在某个后缀 z 能把它们分开——所以它的状态恰好就是 ≡ 的等价类；比这更粗会出错，比这更细则是冗余。这使得最小 DFA 是规范的（不像正则表达式或 NFA，它们没有规范形式）。

最干净的非正则性证明

aⁿbⁿ：前缀 a⁰, a¹, a², … 是两两可区分的——aⁱ 和 aʲ 被后缀 bⁱ 分开（aⁱbⁱ∈L，aʲbⁱ∉L）。无穷多个等价类 ⇒ 不是正则的。 不需要任何 pumping lemma 式的记账——你只需给出一个无穷的可区分前缀族即可。这通常是证明一个语言不是正则语言的正确工具。