正则语言

形式语言是某个字母表上有限字符串的集合。若存在一台有限自动机，恰好接受集合内的字符串并拒绝其他字符串，这个语言就是正则语言。这里的“有限”限定机器的状态数，不限定输入长度，也不要求语言只含有限多个字符串。

确定有限自动机从指定初态出发，逐个读取符号并按照转移规则改变状态；输入读完时，是否处于接受状态决定结果。例如只检查二进制串是否以 01 结尾，不必保存整段输入：保留与该结尾有关的少量状态便足够。

参考：[1]

形式正则表达式从单个符号、空串和空语言出发，用并、连接与星号运算组合模式。并表示择一，连接表示先后拼接，星号表示重复零次或多次。例如 (0|1)*01 描述所有以 01 结尾的二进制串；其中重复零次也有意义，所以 01 本身属于这个语言。

非确定有限自动机可以有多条可选路径以及不读取输入的空转移，只要某条路径读完整个串并到达接受状态，就接受该串。把同时可能出现的状态集合当作新的状态，可构造等价的确定自动机。正则表达式能转为非确定自动机，有限自动机也能转回表达式，因此这些表示描述的是同一类语言，而非不同等级的计算能力。

参考：[2] [3]

正则语言可以表达无限重复，却不能表达所有看起来简短的规则。先出现任意多个 0，再出现同样多的 1 所组成的语言，就不是正则语言。关键不是规则写得长短，而是有限状态无法为无上限的前半段数量保留各不相同的记忆。

泵引理把这种限制变成证明工具：足够长的接受路径必然重复某个状态，相应的一段输入就可以重复或删去而保持接受。对上述等量规则，适当选取长串后，这种操作会破坏两部分数量的相等。泵引理是正则语言的必要条件，不能仅凭暂时画不出自动机就断言语言非正则。

参考：[3]

软件中的 regex 往往在形式正则表达式之外增加语法。有些只是简写，不改变可描述的语言类别；反向引用则可以要求后文重复前面捕获的任意文本，从而具有超出正则语言的表达能力。不能仅凭接口名称就把所有匹配规则归入正则语言，也不能认为每个使用反向引用的具体模式都必然非正则。

语言类别与执行速度还应分开判断。即使模式描述的是正则语言，不同匹配算法也可能表现悬殊；有限自动机方法与逐条尝试路径的回溯实现并不是同一种执行策略。

参考：[4]