递归定义递归基础空字(\varepsilon)和空集(\varnothing)是正规式字母表(\Sigma)上的单个字符如(0)、(1)、(a)、(b)等也是正规式。递归扩展若(r_1)和(r_2)是正规式则(r_1|r_2)或运算对应集合的并集、(r_1r_2)连接运算对应集合的乘积运算、(r_1^*)闭包运算对应集合的克林闭包以及((r_1))括号改变运算优先级和结合性也都是正规式。物理意义每个正规式都对应一个正规集即由字符串组成的集合正规式是描述正规集的表达式。例如正规式(0)对应正规集({0})正规式(\varepsilon)对应正规集({\varepsilon})空字组成的集合正规式(\varnothing)对应正规集(\varnothing)空集。闭包运算克林闭包定义对于正规式®对应正规集(L®)其闭包运算(r*)对应的正规集是(L®)的**克林闭包**即(L(r*) {\varepsilon} \cup L® \cup L®L® \cup L®L®L® \cup \dots)包含空串和(L®)中字符串的(1)次、(2)次、(3)次……连接的所有可能结果。例如若(r a)对应正规集({a})则(r^*)对应的正规集是({\varepsilon, a, aa, aaa, \dots})由(0)个或多个(a)组成的所有串。若(r a|b)对应正规集({a, b})则(r^*)对应的正规集是({\varepsilon, a, b, aa, ab, ba, bb, aaa, \dots})由(0)个或多个(a)、(b)组成的所有串。性质闭包中一定包含空串(\varepsilon)因为克林闭包定义包含“(0)次连接”即空串。克林闭包运算具有幂等性((r*)* r^*)因为对闭包再做闭包结果还是原闭包的集合。闭包运算与连接、或运算的关系例如(r^* \varepsilon|r|rr|rrr|\dots)且连接运算对或运算满足分配律如(r(s|t) rs|rt)。正规式的等价若两个正规式对应的正规集相同则称这两个正规式等价。例如正规式(b(ab)*)和((ba)*b)等价因为它们对应的正规集都是由字符串(b)开头后续交替出现(ab)或(ba)若干次最后以(b)结尾的所有串可通过展开闭包并分析连接、或运算的结果验证。正规式(a*a)和(a*)(a \neq \varepsilon)等价吗不等价因为(a^a)对应的正规集是({a, aa, aaa, \dots})不含空串而(a^)对应的正规集是({\varepsilon, a, aa, \dots})含空串。闭包与正规闭包的差别结合知识背景理解闭包克林闭包是正规式的运算符作用于正规式®生成新的正规式(r^*)其对应的正规集是(L®)的克林闭包包含空串和(L®)中字符串的任意次连接。是语言层面的操作用于构造更复杂的正规式描述更大的字符串集合。正规闭包关系的闭包是关系的闭包如自反闭包、对称闭包、传递闭包定义在集合(A)上的二元关系(R)上满足三个条件包含(R)、具有目标性质如自反性、对称性、传递性、是满足前两个条件的最小关系。是关系层面的操作用于给关系补充缺失的性质如自反性使其满足特定的数学结构如等价关系需要自反、对称、传递性。总结正规式是描述字符串集合正规集的表达式通过递归定义和或、连接、闭包运算构造。闭包克林闭包是正规式的运算符生成包含空串和原集合字符串任意次连接的新集合。正规式的等价性由正规集是否相同决定可通过分析闭包、连接、或运算的结果验证。闭包克林闭包是语言层面的操作而正规闭包关系闭包是关系层面的操作二者的运算对象、目的、性质均不同。闭包运算这里主要讨论正规式的克林闭包和关系的闭包结合知识背景分析具有以下性质一、正规式的克林闭包语言层面的闭包幂等性对于正规式®对应正规集(L®)其克林闭包(r*)满足((r)^ r*)。因为(r)对应的正规集是(L®)的克林闭包包含空串和(L®)中字符串的任意次连接再次对(r^)取闭包不会改变其正规集已包含所有可能的连接组合。例如若(r a)对应正规集({a})则(r^* {\varepsilon, a, aa, aaa, \dots})((r*)* r^*)因为再次闭包后正规集仍为({\varepsilon, a, aa, \dots})。零次幂与闭包的关系正规式(r)的克林闭包(r*)包含(r)的**零次幂**即空串(\varepsilon)对应的正规集({\varepsilon})而(r)的正闭包(r)(r^ r r*)不包含零次幂即(r r | r r | r r r | \dots)仅包含(r)中字符串的(1)次、(2)次……连接的结果。例如(r a)时(r^* {\varepsilon, a, aa, \dots})(r^ {a, aa, aaa, \dots})。与连接、或运算的兼容性连接运算对克林闭包满足分配律左分配和右分配。例如(r(s^) (rs)*)左分配((s)r (sr)*)右分配不严格来说(r(s) rs^0 | rs^1 | rs^2 | \dots {\varepsilon r} | rs | rs^2 | \dots r | rs | rs^2 | \dots)而((rs)^ {\varepsilon} | rs | (rs)(rs) | \dots)二者不一定相等。正确的关系是(r*s* \subseteq (rs)*)不成立((rs)* \subseteq r*s)也不成立但((r|s)^ r*s)当(r)和(s)的正规集不交时不实际((r|s)^ {\varepsilon} | (r|s) | (r|s)(r|s) | \dots)而(r*s* ({\varepsilon} | r | r^2 | \dots)({\varepsilon} | s | s^2 | \dots))二者相等因为((r|s)^n \bigcup_{i j n} r^i s^j)(n \geq 0)所以((r|s)^* \bigcup_{n 0}^\infty (r|s)^n \bigcup_{n 0}^\infty \bigcup_{i j n} r^i s^j (\bigcup_{i 0}^\infty r^i)(\bigcup_{j 0}^\infty s^j) r*s*)。或运算与克林闭包的关系((r|s)^* r*s*)当(r)和(s)的正规集的连接不产生新字符串时实际如上述推导((r|s)*)和(rs^)的正规集相等。二、关系的闭包关系层面的闭包如自反闭包、对称闭包、传递闭包最小性关系®的闭包如自反闭包(r®)、对称闭包(s®)、传递闭包(t®)是满足以下三个条件的最小关系包含原关系(R)即(R \subseteq)闭包关系具有目标性质如自反性、对称性、传递性是满足前两个条件的最小关系若存在另一个关系(S)也满足前两个条件则闭包关系(\subseteq S)。例如®是集合(A)上的关系其自反闭包(r®)是在®中添加所有形如((a, a))(a \in A)的有序对后的关系且是包含®的最小自反关系。自反闭包的性质若®是自反的则(r® R)因为®已满足自反性无需添加有序对(r®)的关系矩阵的主对角线元素全为(1)自反性的矩阵特征。对称闭包的性质若®是对称的则(s® R)因为®已满足对称性无需添加逆有序对(s®)的关系矩阵是对称矩阵对称关系的矩阵特征即若((a, b))在(s®)中则((b, a))也在(s®)中。传递闭包的性质若®是传递的则(t® R)因为®已满足传递性无需添加由传递性推导的有序对传递闭包(t®)可通过“沃舍尔算法”或“逐次求并(R^n)(n \geq 1)”计算即(t® R \cup R^2 \cup R^3 \cup \dots)(R^n)是®的(n)次复合。例如(R {(a, b), (b, c)})则(R^2 {(a, c)})(t® {(a, b), (b, c), (a, c)})。三、闭包与其他运算的关系跨层面的性质正规式闭包与关系闭包的区别正规式的克林闭包是语言字符串集合的操作用于构造更复杂的正规式描述更大的字符串集合关系的闭包是关系的操作用于给关系补充缺失的性质如自反性、传递性使其满足特定的数学结构如等价关系需要自反、对称、传递性。闭包的“继承性”若原关系/正规式具有某些性质其闭包可能继承部分性质。例如若关系®是自反且传递的则其传递闭包(t® R)因为®已满足传递性若正规式®对应的正规集(L®)是有限集则其克林闭包(r^)对应的正规集可能是无限集如(r a)(L® {a})(r^ {\varepsilon, a, aa, \dots})是无限集。总结闭包运算包括正规式的克林闭包和关系的闭包的核心性质是最小性关系闭包和幂等性正规式闭包同时闭包与原运算/关系的性质如自反性、传递性、语言的连接性密切相关且不同层面的闭包语言 vs 关系具有不同的应用场景和数学意义。