克莱因星

在数理逻辑和计算机科学中，克莱因星（或克莱因算子或克莱因闭合）是一种单项运算，可以是对字符串集的运算，也可以是对符号或字符集的运算。在数学上，它更多地被称为自由单体结构。克莱因星对一个集合的应用是{displaystyleV{*}}。.它被广泛用于正则表达式，这也是StephenKleene引入它来描述某些自动机的背景，其中它意味着零或更多的重复。如果V{displaystyleV}是一组字符串，那么是一个字符串集，那么{displaystyle/varepsilon}，并且在字符串连接操作下是封闭的。并且在字符串连接操作下是封闭的。{displaystyleV{*}}是符号或字符的集合。中的符号的所有字符串的集合。V{displaystyleV}的所有字符串的集合。的所有字符串的集合，包括空字符串{displaystyleV{*}}也可以描述为包含空字符串和所有有限长度的字符串的集合，这些字符串可以通过连接任意长度的字符串生成。也可以被描述为包含空字符串和所有有限长度的字符串的集合，这些字符串可以通过连接任意的V{displaystyleV}.的任意元素连接而生成的所有有限长度的字符串，允许多次使用同一元素。如果V{displaystyleV}是空集∅或单子集。是空集∅或单子集{ε}{displaystyle{varepsilon}}，那么V{displaystyleV}要么是空集∅，要么是单子集{ε}。

{displaystyleV}是任何其他有限集或可数无限集，那么是任何其他有限集或可数无限集，那么{displaystyleV{*}}是一个可数无限集。是一个可数无限集。因此，在有限或可数无限的字母表上的每个形式语言Σ{displaystyleSigma}上的每一种形式语言都是可数的。是可数的，因为它是可数无限集的一个子集{displaystyleΣ{*}}。这些运算符被用于生成语法的重写规则中。

给定一个集合{displaystyleV{0}={{varepsilon}}。并递归地定义集合{displaystyleV{i}}可以被理解为所有可以被表示为连接的字符串的集合。可以理解为所有可以被表示为i{displaystylei}的字符串的连接。中的字符串的连接。

字符串构成一个单体，连接是二元操作，ε是身份元素。克莱因星是为任何单体定义的，而不仅仅是字符串。更确切地说，让(M,⋅)是一个单体，并且S⊆M。