正则语言的性质

一、正则语言的性质

1.正则语言的泵引理

设$L$是正则语言，则存在与$L$相关的常数$n$满足：对于任何$L$中的串$w$，如果$|w|\ge n$，则我们就能把$w$打断为三个串$w=xyz$使得：

1. $y\ne ϵ$。
2. $|xy|\le n$。
3. 对于所有的$k\ge 0$，串$x{y}^{k}z$也属于$L$。

也就是说，我们总能在离$w$的开始处不远的地方，找到一个非空串$y$，然后可以把它作为“泵”，也就是说，重复$y$任意多次，或者去掉它（$k=0$），而所得到的结果串仍属于$L$。

2.泵引理的应用

泵引理主要用于证明某个语言是非正则的。主要步骤如下：

1. 选择一个给定的需要证明的非正则语言$L$。
2. 选择一个合适的$n$，注意这里$n$并不是某个常数，而是要考虑任何可能的$n$。
3. 选择串$w$，它可以与$n$相关，且长度至少为$n$。
4. 把$w$拆分成$x,y,z$，同时满足泵引理中规定的限制条件：$y \not= \epsilon $以及 $ |xy| \leq n$。
5. 如果能够选择任意$k\ge 0$使得$x{y}^{k}z$不属于$L$，其中$k$可以是$n,x,y,z$的函数，则能够证明$L$不是正则语言。

证明下面的语言不是正则语言：

例1 { w w ∣ w ∈ { 0 , 1 } ∗ } \{ww\mid w \in \{0,1\}^*\} {ww∣w∈{0,1}∗}

证明：

假设 L = { w w ∣ w ∈ { 0 , 1 } ∗ } L=\{ww\mid w \in \{0,1\}^*\} L={ww∣w∈{0,1}∗}是正则语言。
对于给定的$n$，构造串$w=0^{n}10^n\in L$。
根据正则语言的泵引理，将$w$分割为$w=xyz$，且使得$|xy|<n,y \not= \epsilon $。易知，$y=0^k(0<k\leq n)$，且$w_i = xy^iz \in L$。令$i = 2$，则$w_2=0^{n+k}10n1 \notin L$，得出矛盾，故$L$不是正则语言。

例2 { w ∣ ∣ 0 ∣ w ≥ ∣ 1 ∣ w , w ∈ { 0 , 1 } ∗ } \{w\mid |0|_w\geq |1|_w,w\in \{0,1\}^*\} {w∣∣0∣w​≥∣1∣w​,w∈{0,1}∗}

证明：

假设 L = { w ∣ ∣ 0 ∣ w ≥ ∣ 1 ∣ w , w ∈ { 0 , 1 } ∗ } L=\{w\mid |0|_w\geq |1|_w,w\in \{0,1\}^*\} L={w∣∣0∣w​≥∣1∣w​,w∈{0,1}∗}是正则语言。
对于给定的$n$，构造串$w=1^n{0}^n\in L$。
根据正则语言的泵引理，将$w$分割为$w=xyz$，且使得$|xy|<n,y \not= \epsilon $。易知，$y=1^k(0<k\leq n)$，且$w_i = xy^iz \in L$。令$i = 2$，则$w_2=1^{n+k}0n \notin L$，得出矛盾，故$L$不是正则语言。

例3 { w ∣ ∣ 0 ∣ w + ∣ 1 ∣ w = n 2 , n ∈ N } \{w\mid |0|_w + |1|_w = n^2 ,n \in N\} {w∣∣0∣w​+∣1∣w​=n2,n∈N}

证明：

假设 L = { w ∣ ∣ 0 ∣ w + ∣ 1 ∣ w = n 2 , n ∈ N } L=\{w\mid |0|_w + |1|_w = n^2 ,n \in N\} L={w∣∣0∣w​+∣1∣w​=n2,n∈N}是正则语言。
对于给定的$n$，构造串$w=0^n{1}^{n^2-n}\in L$。
根据正则语言的泵引理，将$w$分割为$w=xyz$，且使得$|xy|<n,y \not= \epsilon $。易知，$y=0^k(0<k\leq n)$，且$w_i = xy^iz \in L$。令$i = 2$，则$w_2=0^{n+k}1{n^2-n} \notin L$，得出矛盾，故$L$不是正则语言。

例4 { 0 x ∣ x is a prime number } \{0^x \mid \text{x is a prime number}\} {0x∣x is a prime number}

证明：

假设 L = { 0 x ∣ x is a prime number } L=\{0^x \mid \text{x is a prime number}\} L={0x∣x is a prime number}是正则语言。
对于给定的素数$n$，构造串$w=0^n\in L$。
根据正则语言的泵引理，将$w$分割为$w=xyz$，且使得$|xy|<n,y \not= \epsilon $。易知，$y=0^k(0<k\leq n)$，且$w_i = xy^iz \in L$。令$i = n-k$，则$w’=0^{n-k+k(n-k)}$。由于$n-k+k(n-k)=(n-k)(k+1)$不是一个素数，所以$w’\notin L$，得出矛盾，故$L$不是正则语言。

二、正则语言的判定性质

1.测试正则语言的空性

判定正则语言是否为空（$\varnothing$），考虑正则语言的表述形式：

1. 如果正则语言是$\text{DFA/NFA}$，则判定是否能从初始状态到达接受状态。（可以根据状态和对应的状态转移，使用深度优先遍历进行）

2. 如果正则语言是正则表达式形式，采用下面的式子递归地对正则表达式进行判定：
   假设$R$是正则语言，则：

   • $R=R_1+R_2$。则$L(R)$当且仅当$L(R_1)$为空且$L(R_2)$为空。
   • $R=R_1{R}_2$。则$L(R)$为空当且仅当$L(R_1)$为空或$L(R_2)$为空。
   • $R=R_1^{\ast }$。则$L(R)$不为空；$L(R)$总是至少包含$ϵ$。
   • $R=(R_1)$。则$L(R)$当且仅当$L(R_1)$为空。二者是相同的语言。

三.正则语言的封闭性

正则语言的封闭性有：

1. 两个正则语言的并是正则的。
2. 正则语言的补是正则的。
3. 两个正则语言的交是正则的。
4. 两个正则语言的差是正则的。
5. 正则语言的反转是正则的。
6. 正则语言的闭包（星）是正则的。
7. 几个正则语言的连接是正则的。
8. 正则语言的同态（用串来代替符号）是正则的。
9. 正则语言的逆同态是正则的。

下面是上述定理的简要证明：

1. 如果$L$和$M$都是正则语言，则$L\cup M$也是正则的。

证明 由于$L$和$M$都是正则的，所以它们都有正则表达式，$L=L(R)$，$M=L(S)$，所以$L\cup M=L(R+S)$也是正则的。

2. 如果$L$是字母表$\Sigma$上的正则语言，则$\overline{L}={\Sigma }^{\ast }-L$也是正则语言。

证明 设$A=(Q,\Sigma ,\delta ,q_0,F)$是某个接受$L=L(A)$的$\text{DFA}$，则$\overline{L}=L(B)$，其中$B$是$B=(Q,\Sigma ,\delta ,q_0,Q-F)$。$w$属于$L(B)$当且仅当$w$不属于$L(A)$。

3. 如果$L$和$M$都是正则语言，则$L\cap M$也是正则的。

证明 由德摩根律，$L\cap M=\overline{\overline{L}\cup \overline{M}}$。由正则语言在并和补下的封闭性知，$L\cap M$也为正则语言。

我们可以通过乘积构造法构造接受$L\cap M$的自动机$A$：
$$A=(Q_L\times Q_M,\Sigma ,\delta ,(q_L,q_M),F_L\times F_M)$$
其中，$\delta ((p,q),a)=({\delta }_L(p,a),{\delta }_M(q,a))$。

则$A$接受$w$当且仅当$w\in L$且$w\in M$。

4. 如果$L$和$M$是正则语言，则$L-M$也是正则语言。

证明 注意到$L-M=L\cap \overline{M}$。由正则语言在交和补上的封闭性知，$L-M$也是正则语言。

5. 如果$L$是正则语言，则$L^R$（$R$的反转）也是正则语言。

证明 设$L$由正则表达式$E$定义，则对$E$的长度进行归纳。

基础 如果$E$是$ϵ$、$\varnothing$或者某个符号$a$，则$E_R=E$。

归纳 根据$E$的形式，分为一下三种情况：

1. $E=E_1+E_2$，则$E^R=E_1^R+E_2^R$。
2. $E=E_1{E}_2$，则$E^R=E_2^R{E}_1^R$。
3. $E=E_1^{\ast }$，则$E^R=(E_1^R{)}^{\ast }$。

同样地，也可以构造自动机来证明该封闭性。给定一个正则语言$L$的自动机$L(A)$，通过下列方法构造$L^R$的自动机：

1. 把$A$的状态转移图中所有箭弧反转。
2. 新自动机惟一的接受状态是$A$的初始状态。
3. 创建一个新的初始状态$p_0$，同时从该状态出发到所有$A$的接受状态都建立一个$ϵ$转移。

6. 如果$L$是正则语言，则$L^{\ast }$也是正则语言。

证明 由于$L$是正则的，所以它有正则表达式$L=L(R)$，所以$L^{\ast }=L(R^{\ast })$也是正则的。

7. 如果$L$是正则语言，$M$是正则语言，则$LM$是正则语言。

证明 由于$L$和$M$都是正则的，所以它们都有正则表达式，$L=L(R)$，$M=L(S)$，所以$LM=L(RS)$也是正则的。

8. 如果$L$是字母表$\Sigma$上的正则语言，$h$是字母表$\Sigma$上的一个同态，则$h(L)$也是正则的。

证明 串同态是串的函数，它对于每一个符号用一个特别的串来替换。

设$L=L(R)$，其中$R$是正则表达式。用结构归纳法来证明上述结论：取出$R$的一个子表达式$E$，并对它应用$h$得到$h(E)$，那么$L(h(E))=h(L(E))$。

基础 如果$E$是$ϵ$或者$\varnothing$，$h(E)=E$。因此$L(h(E))=h(L(E))$。

如果$E=a$，$a$为$\Sigma$中的一个符号，此时$L(E)=a$，$h(L(E))=h(a)$，因此$L(h(E))=h(L(E))$。

归纳

• $E=F+G$：$L(h(E))=L(h(F)+h(G))=L(h(F))\cup L(h(G))$。
• $E=F^{\ast }$：$L(h(E))=L(h(F^{\ast }))=L(h(F{)}^{\ast })=L(h(F){)}^{\ast }$。
• $E=FG$：$L(h(E))=L(h(FG))=L(h(F)h(G))=L(h(F))L(h(G))$。

而$L(h(F)),L(h(G))$都可以通过基础归纳证明是正则语言，故$h(L)$也是正则语言。

9. 如果$h$是字母表$T$到字母表$T$的同态，且$L$是字母表$T$上的正则语言，那么$h^{-1}(L)$也是正则语言。

证明 从$L$的一个$\text{DFA A}$和$h$出发，构造一个$h^{-1}(L)$的$\text{DFA B}$。

该$\text{DFA}$使用$A$的状态，但转移前把输入符号按照$h$转移一下。

设 DFA A = { Q , T , δ , q 0 , F } \text{DFA A}=\{Q,T,\delta,q_0,F\} DFA A={Q,T,δ,q0​,F}，则$B=(Q,\Sigma ,\gamma ,q_0,F)$。

其中$\gamma (q,a)=\delta (q,h(a))$。

四、正则语言的等价性

给定两个正则语言$L$和$M$，可以通过乘积构造法来判断它们接受的语言是否相同。

设$L=L(R)$，$M=L(S)$。$R$和$S$分别为接受$L$和$M$的自动机。

我们不妨假设它们的字母表相同（不同可以取并）。

设$R=(Q,\Sigma ,{\delta }_R,q,F_R)$；$S=(S,\Sigma ,{\delta }_R,s,F_S)$。

按照下面的方法构造一个乘积$\text{DFA T}$。

$T=(R\times S,\Sigma ,{\delta }_T,[r,s],F_T)$。

其中，${\delta }_T([q,s],a)=[{\delta }_R(q,a),{\delta }_S(s,a)]$。

$F_T$是由下面的状态对构成的集合：

$[r,s]$当且仅当$r$和$s$中只有一个是接受状态。

那么$L=M$当且仅当$L(B)=\varnothing$。因为$L=M$当且仅当对于任意$w\in L$，$w\in M$且对于任意$w\notin L$，$w\notin M$。（即不存在一个串$w$，使得它属于一方而不属于另一方）

通过测试$\text{DFA B}$的空性即可确定最终$L$与$M$的等价性。