正规表达式

运算符

• 并：$L\cup M$
• 连接：$LM$
• 闭包：$L^{\ast }={\cup }_{i\ge 0}{L}^i$

归纳定义

基础：

1. 常量 $ϵ,\varnothing$ 为正则表达式，分别表示 $\left\{ϵ\right\}$ 和 $\varnothing$
2. $a$ 是任意符号，则 $\mathbf{a}$ 是正则表达式，表示 $\left\{a\right\}$
3. 变量用大写符号表示 归纳：
4. $E$ 和 $F$ 都是正则表达式，则 $E+F$ 是正则表达式
5. $E$ 和 $F$ 都是正则表达式，则 $EF$ 是正则表达式
6. $E$ 是正则表达式，则 $E^{\ast }$ 是正则表达式
7. $E$ 是正则表达式，则 $(E)$ 是正则表达式

优先级

• 闭包
• 连接
• 并

正规语言

对于 $\Sigma$ 上的语言 $R$，若存在 $\Sigma$ 上的正规表达式满足 $L(E)=R$，则称 $R$ 是正规语言。

代数定律

交换律和结合律

• 并满足交换律和结合律
• 连接只满足结合律

单位元和零元

• $\varphi$ 是并的单位元，是连接的零元
• $ϵ$ 是连接的单位元

分配律

• $L(M+N)=LM+LN$
• $(M+N)L=ML+NL$

幂等律

• $L+L=L$

其他

• $(L^{\ast }{)}^{\ast }=L^{\ast }$
• ${\varnothing }^{\ast }=ϵ$
• ${ϵ}^{\ast }=ϵ$
• $L^{+}=L{L}^{\ast }=L^{\ast }L$
• $L^{\ast }=L^{+}+ϵ$
• $L?=L+ϵ$

正规表达式设计

例 1

$L(E)=\left\{w||w|=2\wedge 第二个字符是1\right\}$

---

$(0+1)1$

例 2

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w至少包含3个连续的0\right\}$

---

$(0+1{)}^{\ast }000(0+1{)}^{\ast }$

例 3

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w以01结尾\right\}$

---

$(0+1{)}^{\ast }01$

例 4

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w首尾字符相同\right\}$

---

$0(0+1{)}^{\ast }0+1(0+1{)}^{\ast }1+0+1$ 注意只有单字符的情况！

例 5

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w由交替的0和1组成\right\}$

---

$(01{)}^{\ast }+(10{)}^{\ast }+0(10{)}^{\ast }+1(01{)}^{\ast }=(ϵ+1)(01{)}^{\ast }(ϵ+0)$

例 6

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w倒数第5个位置是1\right\}$

---

$(0+1{)}^{\ast }1(0+1{)}^4$

例 7

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w前5位至少包含1个1\wedge |w|\ge 1\right\}$

---

$(0+1+ϵ{)}^{4}1(0+1{)}^{\ast }$

例 8

$\Sigma =\left\{0,1,2\right\},L(E)=\left\{w|w至少包含一个0和一个1\right\}$

---

分两种情况， 若第一个 0 在第一个 1 前，$2^{\ast }0(0+2{)}^{\ast }1(0+1+2{)}^{\ast }$， 若第一个 1 在第一个 0 前，$2^{\ast }1(1+2{)}^{\ast }0(0+1+2{)}^{\ast }$， 因此最终结果是 $2^{\ast }0(1+2{)}^{\ast }1(0+1+2{)}^{\ast }+2^{\ast }1(1+2{)}^{\ast }0(0+1+2{)}^{\ast }$

例 9

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w中每对相邻的0都出现在相邻的1前\right\}$

---

将字符串分为两部分，前一部分允许出现相邻的 0，但不允许出现相邻的 1，后一部分则相反。 对于前一部分，不允许出现相邻的 1，即 1 后面必然跟着 0：$(10+0{)}^{\ast }(ϵ+1)$ 后一部分同理：$(01+1{)}^{\ast }(ϵ+0)$ 最终结果：$(10+0{)}^{\ast }(ϵ+1)(01+1{)}^{\ast }(ϵ+0)$

例 10

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w=xy\wedge x,y\in {\left\{0,1\right\}}^{\ast }\wedge |y|=3\wedge y=y^R\right\}$

---

$(0+1{)}^{\ast }(000+010+101+111)$

例 11

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w既不包含00也不包含11\right\}$

---

0,1 必然交替出现。 $(ϵ+1)(01{)}^{\ast }(ϵ+0)$

例 12

$\Sigma =\left\{0,1\right\},L(E)=\left\{0^m{1}^n|m,n\ge 0\wedge m+n是偶数\right\}$

---

要么 m, n 均为奇数，要么 m, n 均为偶数： $(00{)}^{\ast }(11{)}^{\ast }+(00{)}^{\ast }01(11{)}^{\ast }=(00{)}^{\ast }(ϵ+01)(11{)}^{\ast }$

例 13

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w以0结尾时，|w|为奇数\wedge |w|\ge 1\right\}$

---

$((0+1{)}^2{)}^{\ast }0+(0+1{)}^{\ast }1$ 注意这种写法 $((0+1{)}^2{)}^{\ast }$

例 14

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w的前5位至少有一个子串00\wedge |w|\ge 2\right\}$

---

$(0+1+ϵ{)}^{3}00+(0+1{)}^{\ast }$

例 15

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w的第2位到第5位至少有一个1\wedge |w|\ge 2\right\}$

---

$(0+1)(0+ϵ{)}^{3}1(0+1{)}^{\ast }$

例 16

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w至少包含3个1\wedge w倒数第3位为1\right\}$

---

$0^{\ast }10^{\ast }1(0+1{)}^{\ast }1(0+1{)}^2$

例 17

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w中的每个1仅出现在一个由奇数个1构成的极大子串中\right\}$

---

$0^{\ast }(1(11{)}^{\ast }00^{\ast }{)}^{\ast }(1(11{)}^{\ast }+ϵ)$

例 18

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w中出现且仅出现一次00\right\}$

---

00 子串的前后都有 0 后面必须接 1：$(1+01{)}^{\ast }00(10+1{)}^{\ast }$

例 19

$\Sigma =\left\{0,1\right\},L(E)=\left\{w|w中不包含子串00和10\right\}$

---

显然 0 只能出现在首位： $(0+ϵ)1^{\ast }$

代数定律的具体化

• 具体化：将正规表达式中的每个变量用单个符号替换
• 一般化：将具体表达式中的单个符号用变量表示
• 应用：用于发现和测试关于正规表达式的定律 $E$ 为正规表达式，$L_1,L_2,\dots ,L_m$ 为其中的变量，将每个 $L_i$ 替换为符号 $a_i$，得到具体表达式 $C$

正规语言的泵引理

对于 $n$ 个状态的 DFA，考虑一个字符串 $w\in {\Sigma }^{\ast }$，$|w|=m\ge n$，$p_i$ 为长度为 $i$ 的前缀通过 DFA 到达的状态，由鸽巢原理，$p_0,p_1,\dots p_n$ 中至少有两个状态重复。

Pumping 特性

$w\in L(D)$，$p_i=p_j$，令 $w=xyz$，其中 $x=a_1{a}_2\dots a_i$，$y=a_{i+1}\dots a_j$，$z=a_{j+1}\dots a_m$，则 $\forall k>0$，有 $x{y}^{k}z\in L(D)$。

Example

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of = q0] (q1) {$q_1$};
		\node [state, accepting, right of = q1] (q2) {$q_2$};
		\draw (q0) edge[loop above, above] node{1} (q0)
			(q0) edge[above] node{0} (q1)
			(q1) edge[above] node{1} (q2)
			(q1) edge[above, loop above] node{0} (q1)
			(q2) edge[above, loop above] node{0,1} (q2);
	\end{tikzpicture}
\end{document}

考查三个字符串：

• $w=101$，$q_0$ 重复出现，将 $w$ 拆分成 $x=ϵ,y=1,z=01$，则 $1^{k}01\in L$
• $w=001$，$q_1$ 重复出现，$x=0,y=0,z=1$，$00^{k}1\in L$
• $w=010$，$q_2$ 重复出现，$x=01,y=0,z=ϵ$，$010^k\in L$

正规语言的泵引理

设 $L$ 是正规语言，则存在常数 $n\ge 1$，使得任一 $w\in L$，$|w|\ge n$ 都可以写成 $w=xyz$，且：

• $y\ne ϵ$
• $|xy|\le n$
• $\forall k\ge 0,x{y}^{k}z\in L$

可用于证明某个语言不是正规语言：

1. 考虑任意的 $n\ge 1$
2. 找到 $w\in L\wedge |w|\ge n$
3. 任选满足 $w=xyz,y\ne ϵ,|xy|\le n$ 的 $x,y,z$
4. 找到一个 $k\ge 0,x{y}^{k}z\notin L$

Example

证明 $L=\{0^m{1}^m|m\ge 0\}$ 不是正规语言。

若是，则存在 $n$ 满足泵引理。 取 $w=0^n{1}^n$，令 $w=xyz$，由于 $y\ne ϵ\wedge |xy|\le n$，$x,y$ 均由 $0$ 组成，且 $x$ 中 0 的个数小于 $n$，取 $k=0$，应有 $xz\in L$，但 $z$ 中 1 的个数显然大于 $x$ 中 0 的个数，因此 $xz\notin L$，矛盾。

Example

$L$ 为满足 0 的数量是 1 的数量的 2 倍的串的语言。

取 $w=0^{2n}{1}^n\in L$，满足 $|w|\ge n$ ，令 $w=xyz$，且 $|xy|\le n\wedge y\ne ϵ$，显然，$x$ 由 0 组成且 0 的个数小于 $n$，取 $k=0$，要使 $xz\in L$，$x$ 中应该包含 $n$ 个 0，矛盾。

• ! 泵引理不是正规语言的充分条件

正规语言的判定性质

判定正规语言是否为空（有限自动机表示）

判定算法：测试从初态是否可达某一终态. 先求所有可达状态的集合，若其中包含终态，则该正规语言非空，否则为空语言。

• 基础：初态是可达的
• 归纳：设状态 $q$ 是可达的，若对于某个输入符号或 $ϵ$，$q$ 可转移到 $p$，则 $p$ 也是可达的

判定正规语言是否为空（正规表达式表示）

• 基础：$L(\varnothing )$ 为空语言，而 $L(ϵ)$ 和 $L(a)$ 不是
• 归纳：
  • $R=R_1+R_2$，$L(R)$ 为空 $\iff L(R_1)$ 和 $L(R_2)$ 都为空
  • $R=R_1{R}_2$，$L(R)$ 为空 $\iff L(R_1)$ 或 $L(R_2)$ 为空
  • $R=R_1^{\ast }$，则 $L(R)$ 非空
  • $R=(R_1)$，$L(R)$ 为空 $\iff L(R_1)$ 为空

判定是否包含特定的字符串

以 DFA 表示正规语言： 从初态开始处理输入 $w$，若可以结束于一个终态，则该正规语言包含 $w$ 以 NFA 或 $ϵ$ -NFA 表示正规语言： 同理进行模拟 以正规表达式表示正规语言： 转化为等价的自动机

判定两个正规语言是否相等

1. 先将两个正规语言的表达形式都转化为 DFA，问题转化为两个 DFA 是否是等价的
2. 适当重命名，使两个 DFA 没有重名的状态
3. 将两个 DFA 相并，构造一个新的 DFA，原来的终态仍是终态，转移边不发生任何变化，取任何一个状态为初态
4. 对新构造的 DFA 运用填表算法，如果原来 DFA 的两个初态不可区别，则这两个正规语言相等，否则不相等

• 全集性：判定补是否为空
• 包含性：$L_1\subseteq L_2$，只需判定 $L_1\cap \overline{L_2}$ 是否为空
• 等价性：判定双向包含

正规语言的封闭运算

并

若 $L$ 和 $M$ 为正规语言，则 $L\cup M$ 为正规语言。 存在正规表达式 $R$ 和 $S$，$L(R)=L,L(S)=M$，因此 $L(R+S)=L(R)\cup L(S)=L\cup M$

补

若 $L$ 为 $\Sigma$ 上的正规语言，则 $\overline{L}={\Sigma }^{\ast }-L$ 也是正规语言。 将 DFA 的终态和非终态反转即可。

交

若 $L$ 和 $M$ 为正规语言，则 $L\cap M$ 是正规语言。 $L\cap M=\overline{\overline{L}\cup \overline{M}}$ 设 $L$ 和 $M$ 是正规语言，定义

$$T=\{w\in L|对于某个y\in M,w和y含有同样个数的1\}$$

Example

设 $A_L=(Q_L,\Sigma ,{\delta }_L,q_L,F_L)$ 和 $A_M=(Q_M,\Sigma ,{\delta }_M,q_M,F_M)$ 为 $L$ 和 $M$ 的 DFA，构造 $ϵ$ - NFA

$$A=(Q_L\times Q_M,\Sigma ,\delta ,(q_L,q_M),F_L\times F_M)$$

其中

$$\delta ((p,q),a)=\{\begin{array}{rlr}& ({\delta }_L(p,0),q),& a=0\\ & ({\delta }_L(p,1),{\delta }_M(q,1)),& a=1\\ & (p,{\delta }_M(q,0)),& a=ϵ\end{array}$$

该 $ϵ$ - NFA 识别 $T$

差

若 $L$ 和 $M$ 是正规语言，则 $L-M$ 是正规语言。 $L-M=L\cap \overline{M}$

连接

若 $L$ 和 $M$ 是正规语言，则 $LM$ 是正规语言。 存在正规表达式 $R$ 和 $S$，$L(R)=L,L(S)=M$，因此 $L(RS)=L(R)L(S)=LM$

星闭包

若 $L$ 是正规语言，则 $L^{\ast }$ 也是正规语言。 存在正规表达式 $R$，$L(R)=L$，因此 $L(R^{\ast })=(L(R){)}^{\ast }=L^{\ast }$

反转

若 $L$ 是正规语言，则 $L^R$ 也是正规语言。 对 DFA 的每条转移弧反转，将初态作为终态，新增一个状态 $p_0$ 作为初态，且 $p_0$ 到任一终态有一 $ϵ$ 转移弧。

同态

设映射 $h:\Sigma \to T^{\ast }$，对 $w=a_1\dots a_n\in {\Sigma }^{\ast }$，定义

$$h(w)=h(a_1)\dots h(a_n)$$

定义 $L$ 的同态

$$h(L)=\{h(w)|w\in L\}$$

若 $L$ 为正规语言，则 $h(L)$ 也是正规语言。 存在正规表达式 $E$ 使 $L(E)=L$，

• 基础：若 $E$ 为 $ϵ,\varnothing$，取 $h(E)=E$，显然 $L(h(E))=h(L(E))$，若 $E$ 为 a，取 $h(E)=h(a)$，有 $L(h(E))=h(L(E))=\{h(a)\}$
• 归纳：对于 $E=E_1{E}_2,E=E_1+E_2,E=E_1^{\ast }$ 分别构造即可

逆同态

记映射 $h:\Sigma \to T^{\ast }$，定义 $L$ 的逆同态

$$h^{-1}(L)=\{w\in {\Sigma }^{\ast }|h(w)\in L\}$$

若 $L$ 为正规语言，则 $h^{-1}(L)$ 也是正规语言。 DFA $A=(Q,T,\delta ,q_0,F)$，$L(A)=L$，构造 DFA $B=(Q,\Sigma ,\gamma ,q_0,F)$，其中 $\gamma (q,a)={\delta }^{\prime }(q,h(a))$

应用

证明某个语言不是正则语言。

Example

$L=\{a^i{b}^j{c}^k|若i=1则j=k\}$

注意，不能通过泵引理证明 $L$ 不是正规语言： 取 $n=2$，对于任意长度大于 2 的 $w$，取 $x=ϵ$，若 $i=2$，取 $y=aa$，否则取 $y$ 为 $w$ 的第一个字符，$z$ 为剩余部分，则有 $w=xyz$。 此时，

• 若 $i=0$，显然 $x{y}^{k}z\in L$
• 若 $i=1$，$y=a$，容易验证 $x{y}^{k}z\in L$
• 若 $i=2$，$y=aa$，$x{y}^{k}z$ 中 $a$ 的个数必然不为 1，$x{y}^{k}z\in L$
• 若 $i>2$，$z$ 中 $a$ 的个数大于 1，$x{y}^{k}z\in L$ 因此满足泵引理。

若 $L$ 为正规语言，则

$$L^{\prime }=L\cap L(a{b}^{\ast }c)=\{a{b}^j{c}^k|j,k\ge 0\wedge j=k\}$$

为正规语言。 设 $h(a)=ϵ,h(b)=0,h(c)=1$，则

$$h(L^{\prime })=\{0^n{1}^n|n\ge 0\}$$

为正则语言，不成立。 因此 $L$ 不是正规语言。

Example

证明 $L=\{a^m{b}^n|m,n\ge 0,m\ne 2n\}$ 不是正规语言

若是，则

$$L^{\prime }=L(a^{\ast }{b}^{\ast })-L=\{a^m{b}^n|m,n\ge 0,m=2n\}$$

是正规语言。 设 $h(0)=aa,h(1)=b$，则

$$h^{-1}(L^{\prime })=\{0^n{1}^n|n\ge 0\}$$

是正规语言，不成立。

Example

证明 $L=\{w{w}^R|w\in \{a,b{\}}^{\ast }\}$ 不是正规语言

若是，则

$$L^{\prime }=L\cap L((ab{)}^{\ast }(ba{)}^{\ast })=\{(ab{)}^m(ba{)}^m|m\ge 0\}$$

是正规语言。 设 $h(0)=ab,h(1)=ba$，则

$$h^{-1}(L^{\prime })=\{0^n{1}^n|n\ge 0\}$$

是正规语言，不成立。

Attention

证明某个语言不是正规语言的思路：

• 不满足泵引理
• 构造，让它进行若干次正规语言的封闭运算后得到的语言已知不是正规语言（或可通过泵引理证明其不是正规语言）
  • $L=\{0^n{1}^n|n\ge 0\}$ 不是正规语言