正则语言

！！注意正则语言和正则表达式之间的区别与联系！！

# 正则语言的定义

若语言$L$是某个DFA$D$的语言，则称$L$是正则语言：

$L\text{是正则语言}\Leftrightarrow(\exist D=(Q,\Sigma,\delta,q_0,F))(L=\bm L(D))$

# 自动机理论中的典型问题

任何问题都能转化为语言的成员性问题：判断给定的字符串$w$是否属于某个具体的语言$L$

$w\in L?$

# 正则表达式与DFA和正则语言间的等价性

$\begin{aligned} &\text{正则表达式与DFA等价}&\text{正则表达式章节中已经证明}\\ \Rightarrow&\text{正则表达式与正则语言等价}&\text{正则语言定义}\\ \end{aligned}$

# 正则语言的封闭性

• $\emptyset$、$\{\varepsilon\}$都是正则语言
• $\Sigma^*$、$\Sigma^+$是字母表$\Sigma$上的正则语言
• （正则运算）若$L$和$M$都是正则语言，则：
  • （交运算）$\overline M$是正则语言
  • （并运算）$L\cup M$是正则语言
  • （差运算）$L-M$是正则语言
  • （补运算）$\overline L=\Sigma^*-L$是正则语言
  • （连接运算）$LM$是正则语言
  • （闭包运算）$L^*$是正则语言
• （反转运算）若$L$是正则语言，则$L^R=\{w^R|w\in L\}$是正则语言
  • 其中$w^R=(a_1a_2\dots a_n)^R=a_n\dots a_2a_1$
• （同态）若$L$是正则语言，则$h(L)$是正则语言
  • 其中$h(L)$称为语言$L$的同态，定义如下：
    • 当输入为字母$a\in\Sigma$时，$h: \Sigma\rightarrow\Gamma^*$是一个从字母表$\Sigma$到另一个字母表上闭包$\Gamma^*$的映射
    • 当输入为字符串$w\in\Sigma^*$时：$h(\varepsilon)=\varepsilon,h(wa)=h(w)h(a)$
    • 当输入为语言$L\subseteq\Sigma^*$时：$h(L)=\{h(w)|w\in L\}$
• （逆同态）若$L$是正则语言，$h^{-1}(L)=\{w\in\Sigma^*|h(w)\in L\}$是正则语言

证明略。

# 正则语言的必要条件：泵引理

对于任意正则语言，总能找到一个正整数$N$（泵长度），该语言中所有长度大于$N$的字符串$w$可以分为$w=xyz$三部分，其中中间的$y$满足：

• $y$非空
• $y$在前$N$个字符内
• $y$可以不断重复而产生新串$xy^kz$，且产生的所有串都仍然属于该语言

（理解“泵”：通过中间的字符串$y$不断产生新串，就像泵一样）

$L\text{是正则语言}\Rightarrow(\exist N\in\mathbb N_+)(\forall w\in L)(|w|\geq N\rightarrow(\exist y\not =\varepsilon,|xy|<N)(\forall k\geq 0)(xy^kz\in L))$

# 证明

令$N$为DFA$A$的状态数，$L=\bm L(A)$，分两种情况讨论：

# 1' $(\forall w\in L)(|w|<N)$

显然$(|w|\geq N\rightarrow(\exist y\not =\varepsilon,|xy|<N)(\forall k\geq 0)(xy^kz\in L))$成立，因为没有$|w|\geq N$的情况

# 2' $(\exist w\in L)(|w|\geq N)$

1. 任取一个$|w|\geq N$
2. 设$m=|w|,w=a_1a_2\dots a_m$，令$q_i=\hat\delta(q_0,a_1a_2\dots a_i)$表示DFA识别此字符串时读入字符$a_i$所到达的状态。
3. 由于$m\geq N$，加上初始状态一共$N+1$个状态，因此必然存在两个状态相等：$(\exist 0\leq i<j\leq N)(q_i=q_j)$
4. 令：
   • $x=a_1a_2\dots a_{i-1}(i\geq 1)$或$x=\varepsilon(i=0)$
   • $y=a_{i}a_{i+1}\dots a_{j}$
   • $z=a_{j+1}a_{j+2}\dots a_{m}(j\leq m-1)$或$x=\varepsilon(j=m)$
5. 由于$q_i=q_j$，因此让DFA在$q_iq_{i+1}\dots q_j$之间不断循环可以对应出无穷多个字符串，即$xy^kz$

泵引理即证。

# 案例

由正则表达式和正则语言的形式和定义显而易见，正则表达式可以作为正则语言的一种简化的表示方法，在给正则表达式加上一些非正则的操作（例如下面的$\sum_{n=0}^\infty$）后也可以用来表示一些非正则语言。一般以粗体表示正则表达式，大写字母表示语言。

# 证明语言$L=\sum_{n=0}^\infty\bm 0^n\bm 1^n=\{0^n1^n|n\geq 0\}$不是正则语言

反证法：

1. 假设$L$是正则的，那么它满足泵引理
2. 取$w=0^N1^N\in L$，它显然满足$|w|=2N\geq N$
3. 那么对于$y\not =\varepsilon,|xy|<N$：
   • $y$只能取前$N$项
   • $w=0^N1^N$前$N$项全是1
   • 因此$y=0^m,0<m<N$
4. 那么$xy^2z=0^{N+m}1^N\notin L$矛盾
5. 因此$L$不满足泵引理，不是正则语言

# 证明语言$L=\{w|w\text{由数量相等的01构成}\}$不是正则语言

同理，用反证法：

1. 假设$L$是正则的，那么它满足泵引理
2. 取$w=0^N1^N\in L$，它显然满足$|w|=2N\geq N$
3. 同理可以引出$xy^2z=0^{N+m}1^N\notin L$矛盾
4. 因此$L$不满足泵引理，不是正则语言

# 证明语言$L=\{0^i1^j|i>j\}$不是正则语言

同理，用反证法：

1. 假设$L$是正则的，那么它满足泵引理
2. 取$w=0^{N+1}1^N\in L$，它显然满足$|w|=2N+1\geq N$
3. 同理可以引出$y=0^m,0<m<N$
4. 那么$xy^0z=0^{N+1-m}1^N\notin L$矛盾
5. 因此$L$不满足泵引理，不是正则语言

# $\sum_{n=0}^\infty\bm 0^n\bm 1^n$和$\sum_{n=0}^{100}\bm 0^n\bm 1^n$：由非正则语言引发的思考

由上面的第一个案例可以看出，尽管都完全由正则运算构成，$\sum_{n=0}^\infty\bm 0^n\bm 1^n$不是正则语言，而对于语言$\sum_{n=0}^{100}\bm 0^n\bm 1^n$，$\sum_{n=0}^{100}\bm 0^n\bm 1^n$本身就是它的正则表达式，它是正则语言。完全由正则的求和运算运算组成的运算扩展到无穷成为$\sum_{n=0}^\infty$就不是一个正则运算了。

由此我们可以直觉上感觉到DFA的和正则语言的能力限制：“有穷自动机”的“有穷”决定了有穷自动机只能保存有限个状态，而$\sum_{n=0}^\infty\bm 0^n\bm 1^n$这类语言要求自动机记住无穷多个“状态”（记住$0$的数量并将之与$1$的数量进行比较，数量最多可以是无穷多个），因此有穷自动机不能识别。

另外，对于字符串数量有限的语言，必定$(\exist N\in\mathbb N_+)(\forall w\in L)(|w|<N)$，即泵引理必然成立，而其自身也总可以表示为有限个正则表达式的和，因此字符串数量有限的语言必然是正则语言，更加印证了我们对有穷自动机中“有穷”的直觉把握。

那么与有穷自动机相对的，是否存在“无穷自动机”？请见下推自动机。