4.3. 正则文法的封闭性¶
4.3.1. 正则文法的封闭性¶
4.3.1.1. 封闭性概念¶
定义： 一个集合在某种（二元）运算下是 封闭的，如果每当把该运算应用于该集合的任意两个成员时，结果仍是该集合的成员。
4.3.1.2. 正则语言的封闭性¶
考虑正则语言 \(L_1\) 和 \(L_2\)。由于它们是正则语言，我们知道存在正则表达式 \(r_1\) 和 \(r_2\)，使得 \(L_1 = L(r_1)\) 且 \(L_2 = L(r_2)\)。
这些我们已经知道：[问问自己：我们为什么知道这些？]
\(r_1 + r_2\) 是表示 \(L_1 \cup L_2\) 的正则表达式。 因此，正则语言在并（union）运算下是封闭的。
\(r_1r_2\) 是表示 \(L_1 L_2\) 的正则表达式。 因此，正则语言在连接（concatenation）运算下是封闭的。
\(r_1^*\) 是表示 \(L_1^*\) 的正则表达式。 因此，正则语言在星闭包（star-closure）运算下是封闭的。
定理： 正则语言在补（complementation）运算下是封闭的。
证明：
备注
问：为什么用 DFA，NFA 可以吗？答：可以但有困难。它必须是加上陷阱状态（trap states）的完全 NFA。
定理： 正则语言在交（intersection）运算下是封闭的。
证明：
证明这一点的一个简单方法是使用德摩根定律（DeMorgan's Law）：
另一种方法是通过构造法。
备注
思路是构造一个 DFA，使其仅当 \(M_1\) 和 \(M_2\) 都接受时才接受。
4.3.1.3. 正则语言在这些运算下是封闭的¶
反转（Reversal）： \(L^R\)
差（Difference）： \(L_1 - L_2\)
右商（Right quotient）：
定义： \(L_1 \backslash L_2 = \{x\ |\ xy \in L_1\ \mbox{for some}\ y \in L_2\}\)
换句话说，它是 \(L_1\) 中合适字符串的前缀。
定理： 如果 \(L_1\) 和 \(L_2\) 是正则的，那么 \(L_1 \backslash L_2\) 是正则的。
证明： （概要）
存在一个 DFA \(M = (Q, \Sigma, \delta, q_0, F)\)，使得 \(L_1 = L(M)\)。
构造 DFA \(M'=(Q, \Sigma, \delta, q_0, F')\) （除了终止状态外，与 \(M\) 等价）。
备注
非空意味着在开始状态与某个终止状态之间存在一条路径。
证毕。
同态（Homomorphism）：
定义： 设 \(\Sigma, \Gamma\) 是字母表。同态是一个函数 \(h : \Sigma \rightarrow \Gamma^*\)
同态的意思是：用一个字符串替换单个字母。
4.3.1.4. 关于正则语言的问题¶
\(L\) 是一个正则语言。
给定 \(L, \Sigma, w \in \Sigma^*\)，\(w \in L\) 吗？
答案：构造一个 FA，并测试它是否接受 \(w\)。
\(L\) 是空的吗？
例：\(L = \{a^nb^m | n > 0, m > 0\} \cap \{b^na^m | n > 1, m > 1\}\) 是空的。
构造一个 FA。如果从开始状态到某个终止状态存在一条路径，那么 \(L\) 不是空的。
备注
从开始状态出发，对图进行深度优先搜索。
\(L\) 的补是正则的吗？
答案：只需取 DFA，并把终止状态与非终止状态互换。
这很容易！但我们会在其他情境中看到，判断补是否正则并不总是这么简单。
\(L\) 是无限的吗？
构造一个 FA。判断从开始状态到终止状态的路径上，是否有某个顶点是某个环（cycle）的基。如果是，那么 \(L\) 是无限的。
注意：DFA 中环（cycle）这个概念以后会很重要！
\(L_1 = L_2\) 吗？
构造 \(L_3 = (L_1 \cap \bar{L_2}) \cup (\bar{L_1} \cap L_2)\)。如果 \(L_3 = \emptyset\)，那么 \(L_1 = L_2\)。
同样，在其他情境中，两个计算表示是否做同样的事情可能是无法回答的。例如，我们将证明：一般而言，无法判定两个程序是否做同样的事情。
4.3.1.5. 小结：如何证明一种语言是正则的？¶
我们的工具箱里有若干方法。
写出接受该语言的 DFA。
写出接受该语言的 NFA。
写出接受该语言的正则表达式。
写出接受该语言的正则文法。
用已知对正则语言封闭的运算符操作一个或多个已知正则语言，来定义该语言。
