形式陈述

语言 $L\subseteq\Sigma^*$$L\subseteq {\mathrm{\Sigma }}^{\ast }$ 称为正则语言，当且仅当存在有限自动机 $M$$M$ 使 $L=L(M)$$L=L(M)$。等价地，$L$$L$ 可由正则表达式描述，也可由右线性文法生成。

直觉

正则语言正好是只需有限记忆就能从左到右识别的模式集合。

例子与边界

所有以 01 结尾的二进制串构成正则语言。括号任意深度匹配和 $0^n1^n$$0^n{1}^n$ 需要无界计数，不是正则语言；泵引理可用来证明这种非正则性。

推论与应用

正则语言对并、交、补、连接和 Kleene 星封闭，支持编译器词法分析、文本搜索和有限协议验证。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., §1.2–1.4.
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Chapter 3.