如何证明一种语言不是正则语言？

最常用的工具是泵引理，它指出正则语言中任何足够长的字符串都包含一个子字符串，该子字符串可以重复任意次，同时仍保持在语言中。找到一个不能以这种方式“泵送”的字符串可以证明该语言不是正则的；Myhill–Nerode 定理通过展示无限多个可区分的前缀提供了另一种论证方法。

如果非确定性自动机并没有更强大的能力，为什么还要使用它们？

它们通常更小，更容易设计或从正则表达式中推导出来。子集构造法可以在需要时将它们转换为确定性形式，尽管这可能会导致状态数量呈指数级增长，因此非确定性是一种方便的规范工具，而不是识别能力的提升。

有限自动机是最简单的计算机器，每次读取一个符号，只使用有限数量的内部状态，它们识别的语言正是正则语言。

用 PaperMind 寻找选题即将推出Find papers & topics

Tools & resources

Learn & explore

视频即将推出

有限自动机是一种具有有限状态集、输入符号上的转移函数、一个起始状态和接受状态的机器；如果读取字符串能使其从起始状态转移到接受状态，则它接受该字符串，并且被接受的字符串集合是它的语言。

本主题涵盖确定性有限自动机和非确定性有限自动机、通过子集构造法证明它们的等价性、正则表达式和克莱尼定理、Myhill–Nerode 定理和状态最小化、正则语言的封闭性，以及用于证明某些语言非正则的泵引理。

子集构造法: 任何非确定性有限自动机都可以通过一个确定性自动机来模拟，该确定性自动机的状态是原始状态的集合，这证明了这两种模型识别的语言完全相同。
克莱尼定理: 当且仅当一种语言可以用正则表达式描述时，它才能被有限自动机识别，这确立了正则语言的机器描述和代数描述的等价性。
Myhill–Nerode 定理: 当且仅当一种语言的字符串不可区分关系具有有限多个等价类时，该语言才是正则的，并且这些等价类决定了该语言唯一的最小确定性自动机。

有限自动机是正则表达式匹配、编译器中的扫描器和词法分析器、文本编辑器中的查找替换以及网络入侵系统中的模式检测的引擎，其中有限内存识别使得处理快速且可预测。

在 McCulloch 和 Pitts 1943 年的神经网络模型的基础上，克莱尼在大约 1951 年描述了有限自动机可以表示的事件，Rabin 和 Scott 在 1959 年形式化了非确定性自动机及其决策问题，这项工作后来获得了图灵奖的认可。

如何证明一种语言不是正则语言？: 最常用的工具是泵引理，它指出正则语言中任何足够长的字符串都包含一个子字符串，该子字符串可以重复任意次，同时仍保持在语言中。找到一个不能以这种方式“泵送”的字符串可以证明该语言不是正则的；Myhill–Nerode 定理通过展示无限多个可区分的前缀提供了另一种论证方法。
如果非确定性自动机并没有更强大的能力，为什么还要使用它们？: 它们通常更小，更容易设计或从正则表达式中推导出来。子集构造法可以在需要时将它们转换为确定性形式，尽管这可能会导致状态数量呈指数级增长，因此非确定性是一种方便的规范工具，而不是识别能力的提升。