Kleene 闭包
| Kleene闭包 | |
|---|---|
| 术语名称 | Kleene闭包 |
| 英语名称 | Kleene closure |
| 别名 | Kleene星号, Kleene星闭包, Kleene*运算符, Kleene star, Kleene operator |
| Kleene正闭包 | |
|---|---|
| 术语名称 | Kleene正闭包 |
| 英语名称 | Kleene plus closure |
| 别名 | Kleene加号, Kleene正闭包, Kleene+运算符, Kleene plus, Kleene+ operator |
Kleene闭包(Kleene closure)指把一个字符串通过连接可能构成的全体字符串集合的运算。 也指将一个字符串集（或形式语言）通过内部元素与连接运算得到的全体可能字符串所构成的新的集合（或形式语言）的运算。
可以理解为这一字符串在连接运算下的最小封闭集合。其中，在原字符串不是空字符串，或者语言中不包含空字符串时，根据构成的是最小幺半群还是最小半群，称为 Kleene 闭包和 Kleene 正闭包。
定义
| Kleene闭包 | |
|---|---|
| 运算名称 | Kleene闭包 |
| 运算符号 | [math]\displaystyle{ ^* }[/math] |
| Latex | ^*
|
| 运算对象 | 字符, 字符串 |
| 运算元数 | 1 |
| 运算结果 | 语言
|
| Kleene正闭包 | |
|---|---|
| 运算名称 | Kleene正闭包 |
| 运算符号 | [math]\displaystyle{ ^+ }[/math] |
| Latex | ^+
|
| 运算对象 | 字符, 字符串 |
| 运算元数 | 1 |
| 运算结果 | 语言
|
对字符串 [math]\displaystyle{ a = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n }[/math] ，称集合 [math]\displaystyle{ \{\varepsilon,a,a^2,a^3,\cdots\}=\{a^n\mid n\in\mathbb{N}\} }[/math] 为字符串的 Kleene 闭包(Kleene closure)，记作 [math]\displaystyle{ a^* }[/math] ；称集合 [math]\displaystyle{ \{a,a^2,a^3,\cdots\}=\{a^n\mid n\in\mathbb{N}^*\} }[/math] 为字符串的 Kleene 正闭包(Kleene plus closure)，记作 [math]\displaystyle{ a^+ }[/math] 。
类似地，也为字符 [math]\displaystyle{ \mathtt{a} }[/math] 定义 [math]\displaystyle{ \mathtt{a}^*=\{\mathtt{a}^n\mid n\in\mathbb{N}\}=\{\varepsilon,\mathtt{a},\mathtt{a}\mathtt{a},\mathtt{a}\mathtt{a}\mathtt{a},\cdots\} }[/math] 和 [math]\displaystyle{ \mathtt{a}^+=\{\mathtt{a}^n\mid n\in\mathbb{N}^*\}=\{\mathtt{a},\mathtt{a}\mathtt{a},\mathtt{a}\mathtt{a}\mathtt{a},\cdots\} }[/math] 。
| Kleene闭包 | |
|---|---|
| 运算名称 | Kleene闭包 |
| 运算符号 | [math]\displaystyle{ ^* }[/math] |
| Latex | ^*
|
| 运算对象 | 语言 |
| 运算元数 | 2 |
| 运算结果 | 语言 |
| 定义域 | [math]\displaystyle{ \mathcal{P}(\Sigma^*) }[/math] |
| 陪域 | [math]\displaystyle{ \mathcal{P}(\Sigma^*) }[/math] |
对语言 [math]\displaystyle{ L }[/math] ，称语言 [math]\displaystyle{ L^0 \cup L^1 \cup L^2 \cup \cdots = \bigcup_{n=0}^\infty L^n }[/math] 为语言的 Kleene 闭包(Kleene closure)，记作 [math]\displaystyle{ L^* }[/math] ；称语言 [math]\displaystyle{ L^1 \cup L^2 \cup \cdots = \bigcup_{n=1}^\infty L^n }[/math] 为语言的 Kleene 正闭包(Kleene plus closure)，记作 [math]\displaystyle{ L^+ }[/math]
字符 [math]\displaystyle{ \mathtt{a} }[/math] 的（正）闭包和字符串 [math]\displaystyle{ a }[/math] 的（正）闭包就是语言 [math]\displaystyle{ \{\mathtt{a}\} }[/math] 和 [math]\displaystyle{ \{a\} }[/math] 的（正）闭包。
等价定义
对给定字符、字符串或语言，包含给定字符、字符串的，或者包含语言中全体元素的语言中，构成关于字符串的连接运算的最小幺半群的称为其 Kleene 闭包(Kleene closure)，构成最小半群的称为其 Kleene 正闭包(Kleene plus closure)。
性质
- 对字母表 [math]\displaystyle{ \Sigma }[/math] 作为语言的 Kleene 闭包就是其上的自由幺半群 [math]\displaystyle{ \Sigma^* }[/math] 。
- 正闭包是普通闭包再次连接一次，即 [math]\displaystyle{ L^+ = L^* L = L L^* }[/math] ，普通闭包是正闭包补充空串 [math]\displaystyle{ L^* = L \cup \{\varepsilon\} }[/math] 。两种闭包相等当且仅当语言中含有空字符串。
- 幂等。 [math]\displaystyle{ (L^*)^*=L^* }[/math] ， [math]\displaystyle{ (L^+)^+=L^+ }[/math] 。
- 特殊取值
- 空语言 [math]\displaystyle{ \varnothing }[/math] ： [math]\displaystyle{ \varnothing^* = \{\varepsilon\} }[/math] ， [math]\displaystyle{ \varnothing^+=\varnothing }[/math]
- 空串语言 [math]\displaystyle{ \{\varepsilon\} }[/math] ： [math]\displaystyle{ \{\varepsilon\}^* = \{\varepsilon\}^+ = \{\varepsilon\} }[/math]