1. 先验知识
设∑为有限字母表，在∑上的正规式与正规集可递归定义如下：
- ε和Ф是∑上的正规式，它们表示的正规集分别为{ε}和Ф；
- 对任何a∈∑, a是∑上的正规式,它的正规集为{a}；
- 若 r,s 都是正规式 , 它们的正规集分别为R和S , 则(r|s)、(r·s)、(r)*也是正规式，它们分别表示的正规集是：R∪S,RS,R*。
- 正规式ε表示的正规集为{ε}
- 正规式Ф表示的正规集为Ф
- 正规式(r|s)表示的正规集为R∪S
- 正规式(r·s)表示的正规集为RS
- 正规式(r)*表示的正规集为R*
![[编译原理] 正规式运算四个特例理解](https://img.it610.com/image/info9/6ce3f5061cf846638ecae978e8c4e523.jpg)
文章图片
因此, 下文特例中正规式运算将用正规集运算, 形象化解释
2. 正文
- ε·A
集合运算为{ε}A=A
因此ε·A=A - ?·A
集合运算为?A=?
因此?·A=? - ε|A
集合运算为{ε}∪A
设A={a1,a2,a3...}
- 若a1,a2,a3...≠ε, {ε}∪A={ε,a1,a2,a3...}
- 若a1=ε, {ε}∪A={a1,a2,a3...}
- ?|A
集合运算为?∪A=A
因此?|A=A
