关于编译原理:编译原理-正规式运算四个特例理解

1. 先验常识

设∑为无限字母表，在∑上的正规式与正规集可递归定义如下：

• ε 和Ф是∑上的正规式，它们示意的正规集别离为 {ε} 和Ф；
• 对任何 a∈∑, a 是∑上的正规式, 它的正规集为{a}；
• 若 r,s 都是正规式 , 它们的正规集别离为 R 和 S , 则(r|s)、(r·s)、(r)* 也是正规式，它们别离示意的正规集是：R∪S,RS,R*。

此处重点为

1. 正规式 ε 示意的正规集为{ε}
2. 正规式Ф示意的正规集为Ф
3. 正规式 (r|s) 示意的正规集为 R∪S
4. 正规式 (r·s) 示意的正规集为 RS
5. 正规式(r)* 示意的正规集为 R *

其中 正规集 RS 应用的是汇合的乘积运算, 定义如下：

因而, 下文特例中正规式运算将用正规集运算, 形象化解释

2. 注释

1. ε·A
   汇合运算为 {ε}A=A
   因而 ε·A=A
2. Ø·A
   汇合运算为ØA=Ø
   因而Ø·A=Ø

3. ε|A
   汇合运算为 {ε}∪A
   设 A ={a1,a2,a3…}

   • 若 a1,a2,a3…≠ε, {ε}∪A={ε,a1,a2,a3…}
   • 若 a1=ε, {ε}∪A={a1,a2,a3…}

   因而 ε | A 后果为正规式 A ’, 正规式 A ’ 的正规集为{ε}∪A

4. Ø|A
   汇合运算为Ø∪A=A
   因而Ø|A=A