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