字母表Σ上的正规式用来描述一种称为正规集的语言。下面是正规式和正规集的递归定义：
（1）ε和φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和φ；
（2）对任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；
（3）假定U和V都是Σ上的正规式，它们所表示的正规集分别记为L（U）和L（V），那么，（U|V）、（U·V）和U*也都是正规式，它们所表示的正规集分别为L（U）∪L（V）、L（U）L（V）（连接积）和（L（U））*（闭包）。
仅由有限次使用上述三步骤而得到的表达式才是Σ上的正规式，仅由这些正规式所表示的集合（即Σ上的语言）才是Σ上的正规集。
正规式的运算符“∣”读为“或”，“·”读为“连接”，“*”读为“闭包”（即任意有限次的自重复连接）；在不致混淆时，括号可以省去，但规定算符的优先顺序为：先“*”，次“·”，最后“∣”。连接符“·”一般可省略不写。
例3.2 当Σ={0，1}时，下面是Σ上的正规式和相应的正规集：
正规式 正规集
（0|1）* 包括空串在内的所有二进制字符串
0（0|1）*0 长度至少为2，以0开始和结束的二进制字符串
0*10*10*10* 所有包含3个1的二进制字符串(www.xing528.com)
例3.3 设Σ={a，b}，试写一个正规式，使其表示的正规集为“不以a开头，但以aa结尾的字符串集合”。
由于Σ={a，b}，若不以a开头，则必以b开头，而结尾由题目已知，中间部分没有限制，为a、b组成的任意长度的字符串。于是，符合题意的正规式为：b（a|b）*aa
若两个正规式所表示的正规集相同，则认为二者是等价的。两个等价的正规式U和V记为U=V。例如，b（ab）*=（ba）*b，（a|b）*=（a*b*）*。
令U、V、W均为正规式，显然，下列关系成立：
（1）交换律：U|V=V|U
（2）结合律：U|（V|W）=（U|V）|W
U(VW)=(UV)W
（3）分配律：U（V|W）=UV|UW
(U|V)W=UW|VW
(4)εU=Uε=U
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
