编译原理

　　正规式定义中的“|”读为“或”（也有使用“+”代替 “|” 的）；“·”读为“连接”；“*”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“(”、“)”、“*”、“·”、“|” 。连接符“·”一般可省略不写。“*”、“·”和“|” 都是左结合的。
　　令∑={a，b}， ∑上的正规式和相应的正规集的例子有：
　　正规式　　　　　　　正规集
　　a 　　　　　　　　　　{a}
　　a|b 　　　　　　　　　{a,b}
　　ab　　　　　　　　　　{ab}
　　(a|b)(a|b)　　　　　　{aa,ab,ba,bb}
　　a^*　　　　　　　　　　{ε,a,a, ……任意个a的串}
　　(a|b)^*　　　　　　　　{ε,a,b,aa,ab ……所有由a和b组成的串}
　　(a|b)^*(aa|bb)(a|b)^*　 {∑^*上所有含有两个相继的a或两个相继的b组成的串}

　　若两个正规式e₁和e₂所表示的正规集相同，则说e₁和e₂等价，写作e₁=e₂。
　　例如： e₁= (a|b)， e₂ = b|a
　　又如： e₁= b(ab)^* ，e₂ =(ba)^* b
　　再如： e₁= (a|b)^* ，e₂ =(a^* |b^* )^*
　　设r,s,t为正规式，正规式服从的代数规律有：
　　① r|s=s|r 　　　　　　"或"服从交换律
　　② r|(s|t)=(r|s) | t 　"或"的可结合律
　　③ (rs)t=r(st) 　　　　"连接"的可结合律
　　④ r(s|t)=rs|rt
　　　 (s|t)r=sr|tr 　　　　分配律
　　⑤ εr=r, rε=r 　　　 ε是"连接"的恒等元素零一律
　　⑥ r|r=r
　　　 r^*=ε|r|rr|…　　　　"或"的抽取律