正规式

字符串集合运算

设 $A,B$ 为字母表 $\Sigma$ 上的字符串集合：

• 乘积：$A\cdot B=\{\alpha \beta \mid \alpha \in A,\beta \in B\}$
• 方幂：$A^n=A\cdot A\cdot \dots \cdot A$（$n$ 次），$A^0=\{\epsilon \}$
• 正闭包：$A^{+}=A^1\cup A^2\cup A^3\cup \dots$
• 自反闭包（Kleene 闭包）：$A^{\ast }=A^0\cup A^{+}={\bigcup }_{n=0}^{\infty }{A}^n$

$\{\epsilon \}\ne \varnothing$，$\{\epsilon \}$ 是含空串的集合，$\varnothing$ 是空集。 $A\cdot \varnothing =\varnothing$，$A\cdot \{\epsilon \}=A$

正规式与正规集

正规式（Regular Expression, RE）递归定义：

1. 基本正规式：$\varnothing$、$\epsilon$、$a$（$a\in \Sigma$）是正规式
2. 归纳构造：若 $r,s$ 是正规式，则：
   • $r|s$（或，对应并集）
   • $r\cdot s$（连接，可省略）
   • $r^{\ast }$（闭包）
   • $(r)$（括号改变优先级） 也是正规式

正规式 $r$ 描述的语言称为正规集，记作 $L(r)$：

• $L(\varnothing )=\varnothing$
• $L(\epsilon )=\{\epsilon \}$
• $L(a)=\{a\}$
• $L(r|s)=L(r)\cup L(s)$
• $L(r\cdot s)=L(r)\cdot L(s)$
• $L(r^{\ast })=(L(r){)}^{\ast }$

运算优先级：() > * > · > |

重点 正规式运算优先级、正规式与正规集的关系。

常见正规式示例

$\Sigma =\{0,1\}$：

• 含 “00” 的串：$(0|1{)}^{\ast }00(0|1{)}^{\ast }$
• 不含 “00” 的串：$(1|01{)}^{\ast }(0|\epsilon )$

$\Sigma =\{A,B,0,1\}$：

• 变量名（字母开头）：$(A|B)(A|B|0|1{)}^{\ast }$
• 有符号整数：$(-|\epsilon )(0|1|2|\cdots |9)(0|1|\cdots |9{)}^{\ast }$
• 浮点数：$(-|\epsilon )(0|1|\cdots |9{)}^{\ast }\cdot (0|1|\cdots |9{)}^{\ast }$

正则定义的代数性质

正规式满足以下代数性质：

性质	表达式
交换律	$r\Vert s=s\Vert r$
结合律	$(r\Vert s)\Vert t=r\Vert (s\Vert t)$，$(rs)t=r(st)$
分配律	$r(s\Vert t)=rs\Vert rt$，$(s\Vert t)r=sr\Vert tr$
幂等律	$r\Vert r=r$
零元	$\varnothing r=r\varnothing =\varnothing$
幺元	$\epsilon r=r\epsilon =r$