正则语言

定义

正则语言是形式语言层级中最简单的一类，指能够被有限状态机识别的语言，等价地，也是能由正则表达式描述或由正则文法生成的语言。这三种刻画方式在表达能力上完全一致，构成了正则语言的多重等价定义。

原理

正则语言在并、连接、闭包以及交、补等运算下保持封闭，这使其便于组合分析。判断某语言是否正则，常借助泵引理：若语言正则，则足够长的字符串必含可重复抽取的子段而仍属于该语言。利用泵引理可证明诸如「左右括号配对」这类需要计数的语言不是正则的。

应用

正则语言因结构简单、识别高效而应用广泛。词法分析器用正则表达式定义编程语言的单词模式，文本编辑器和搜索工具用它进行模式匹配，网络设备用它过滤数据。其局限在于无法处理嵌套结构，因此括号匹配、语法树构建等任务需要更强的上下文无关文法来完成。