正则语言

读完前缀 $x$ 后，识别器只需知道后续哪些字还能使 $xz$ 落入 $L$。若所有前缀能够按这种未来行为归入有限多类，就可用一个状态代表一类；反之，若不断出现需要区别的新前缀，任何固定状态集都会过早遗忘信息。

正则语言擅长有限记忆：是否见过某个标记、当前位置处于有限协议的哪一阶段、计数模固定常数的余数、最近若干字符形成什么后缀。它不擅长无界配对：任意深度的括号、两段长度精确相等、后半段复制前半段。分界不在输入是否很长，而在决定未来时需要保留的信息种类是否有固定上界。

有限自动机中的环解释了正则语言为何可以无限。机器每次回到同一状态，就可以再次处理相似片段；它无需记住环走了多少圈，只需知道当前未来行为没有改变。星号与自动机环正是同一有限记忆现象的代数和图形两种表达。

典型 ASCII 标识符语言由“首字符是字母或下划线，后续字符是字母、数字或下划线”组成。扫描器只需区分起点、已进入合法标识符、已经失败三种情况，不必保存标识符内容，因此该语言正则。保留具体文本供符号表使用是后续处理，不属于判断词法形状所需的控制状态。

包含固定字节模式 \r\n\r\n 的输入也正则。自动机只需记当前后缀与目标模式前缀重合到多长；模式固定时，可能长度有限。即使输入有数 GB，状态数也不随之增长。

语言

不是正则语言，因为读取左括号后必须保留无界深度，才能核对后续右括号。若产品规范把最大嵌套深度固定为 32，它反而成为正则语言：状态可以记录 $0$ 到 $32$ 的当前深度，再加一个溢出/错误状态。理论边界取决于约束是否真正固定，而不是业务上“通常不会太深”。

每个有限语言都是正则语言，可以为所有字建立前缀树并把未匹配输入送入死状态；无限语言也完全可能正则，例如 $0^{\ast }$。因此语言的基数不是判据。泵引理或 Myhill–Nerode 证明的是无界信息需求，而不是简单宣称“集合无限所以不正则”。

实际 regex 引擎也不能反向定义正则类。回溯、捕获和匹配优先级属于实现语义；反向引用等扩展甚至能描述非正则语言。判断一个模式的理论性质时，应先把它还原到明确的经典构造。

正则语言拥有稳定的构造与判定工具。它们对有限布尔运算、连接、星、反转、同态与逆同态封闭；给定 DFA 后，成员资格可在线线性扫描，空性可做可达性搜索，有限性可检查初态到接受态路径上是否存在可重复环，等价与包含可化为乘积图上的空性。

闭包性质公理库正则语言闭包性质Closure properties of regular languages正则语言经有限布尔组合、连接、星、反转以及同态像和逆像后仍是正则语言。负责安全地组合已有识别器；DFA 最小化公理库有限自动机最小化Finite automaton minimization · DFA minimization删除不可达状态并按全部未来后缀的行为划分状态，构造识别同一语言的唯一最小 DFA。给同一语言找到状态最少的规范表示；泵引理公理库正则语言泵引理Pumping lemma for regular languages足够长的正则语言成员必有一段位于短前缀中的非空环，可删除或重复任意多次而仍留在语言中。和 Myhill–Nerode 则从有限记忆的必然后果出发证明某些语言不正则。三类工具分别回答“怎样构造”“怎样压缩”和“为什么做不到”。

持续系统的无限轨迹属于 ${\mathrm{\Sigma }}^{\omega }$。相应的 $\omega$-正则语言以 Büchi 等接受条件描述“运行中无限反复发生什么”，不在读完后检查终态。有限字与无限字模型都使用有限控制，但论域和接受量词不同。