正则语言 (Regular Language) // 圆方

正则语言 (regular language) 是可以用正则表达式或自动机描述的语言，用于解析和设计编程语言。正则语言和有限自动机可以对需要极少量内存的计算问题进行建模。如果有一个有限自动机可以识别一种语言，那么它就是一种正则语言。

正则语言是形式语言 (Formal Language) 的其中一种，如果存在有限的符号集合 ($\Sigma$ 表示)，那么该集合就可以被称为是一种语言。这种定义非常宽泛，区别于我们日常所了解的自然语言。

如果有个集合为空，那么该空集也可以被称为一种语言。可以表示为：$\varnothing$。若有个集合包含一个空字符串 ($ε$ 表示)，那么该集合也是一种语言，可以表示为 $\lbraceε\rbrace$。但是 $\lbraceε\rbrace \not ={\varnothing}$。

正则表达式的形式定义如下：

空集合 $\varnothing$ 是正则语言；
只包含一个空串的语言 $\lbraceε\rbrace$ 是正则语言；
对所有 $a ∈ \Sigma $，$\lbrace a \rbrace$ 是正则语言；
若 $A$, $B$ 是正则语言，则 $A\cdot B$ (concatenation), $A \bigcup B$ (union), $A^{*}$ (kleene star) 都是正则语言。

除此之外都不是正则语言。

正则语言有三种运算：连接 (Concatenation)、并 (Union)、Kleene 星 (Kleene Star)。

Kleene 在 20 世纪 50 年代提出的这三种基本运算符。

通过连接可以把两种或两种以上的语言组合到一起。

若有集合 $L_1 = \lbrace 100, 01 \rbrace$ 和 $L_2 = \lbrace 101,01 \rbrace$，那么通过连接运算后就结果为 $L_1 \cdot L_2 = \lbrace 100101,10001,01101,0101 \rbrace$。

若有集合 $L_1 = \lbrace 100,01 \rbrace$ 和 $L_2 = \lbrace 101,01 \rbrace$，那么通过并运算后结果为 $L_1 \bigcup L_2 = \lbrace 100,01,101 \rbrace$。

Kleene 星运算是一元运算，用 $*$ 表示。它用来重复集合元素任意多次的运算，形式表示：$A^∗ = \lbrace x_1x_2…x_k ∣ k≥0, x_i∈A \rbrace$。

若有集合 $L_1 = \lbrace 100,01 \rbrace$，那么通过Kleene 星运算后结果为 $L_1^* = \lbrace ε,100,100100,100^n,01,01^n,10001100,… \rbrace$，它是一个无穷集合。

开头简介说过正则表达式可以用来描述正则语言。正则表达式可以描述所有通过对某个字母表上的符号应用上面三种运算符而得到的语言。

例子：一个有限集合 $\lbrace 0,1 \rbrace$，我们自定义语言给出一个正则表达式：0(0|1)*1，如果用字母符号和正则语言运算符表示它是这样的：$0\cdot(0 \bigcup 1)^*\cdot1$。

所以以下字符串对于该语言来说语法都是正确的：

如果有一个有限语言 $\lbrace 00,11,010 \rbrace $，那么用 FSM 表示如下：

如果有两个语言：L₁ 用 FSM₁ 表示，L₂ 用 FSM₂，那么对应自动机的三个运算转换如下图所示：

参考资料：