正则表达式和正则语言

正则表达式

• 有穷自动机
  • 通过抽象机器装置扫描和接受字符串识别正则语言
• 正则表达式
  • 通过代数式表示或产生正则语言，便于正则语言的处理
  • 正则表达式所表示的语言与正则语言等价

语言运算

设L和M两个语言，那么

• 并： \(L\cup M=\{w|w\in L 或w\in M\}\)
• 连接：\(L\cdot M\{w|w=xy,x\in L, y\in M\}\)
• 幂： \(L^0=\{\epsilon\},L^1=L,L^n=L^{n-1}\cdot L\)

四则运算

任何数都是四则运算表达式

如果a和b是四则运算表达式，那么

\[a+b,a-b,a\times b,a\div b,(a)\]

都是四则运算表达式

正则表达式的递归定义

• 基础1：\(\phi\)是一个正则表达式，表示空语言\(\phi\)
• 基础2：\(\epsilon\)是一个正则表达式，表示语言\(\epsilon\)

• 基础3：对于任何一个符号a，a是一个正则表达式，表示语言\(\{a\}\)，其中有一个长度为1的字符串

• 归纳1：如果\(E_1,E_2\)是正则表达式，那么\(E_1+E_2\)也是正则表达式，且\(L(E_1+E_2)=L(E_1)\cup L(E_2)\)

• 归纳2：如果\(E_1,E_2\)是正则表达式，那么\(E_1E_2\)也是正则表达式，且\(L(E_1E_2)=L(E_1)L(E_2)\)
• 归纳3：如果E是正则表达式，则\(E^*\)也是正则表达式
• 归纳4：如果E是正则表达式，则\((E)\)也是正则表达式，表示语言\(L(E)\)

正则表达式单则运算以及括号的优先级

\[括号>*>连接>+\]

例：\(1+01*=1+(0(1*))\)

\((1*)=\{\epsilon,1,11,111,1111,\dotsb\}\)

\(0(1*)=\{0,01,011,0111,01111,\dotsb\}\)

\(1+01*=\{1,0,01,011,0111,01111,\dotsb\}\)

代数定律

• 并的交换律
• 并的结合律
• 连接的结合律
• 连接不满足交换律

正则表达式设计

例：设计由0和1组成的正则表达式\(E\)使得

\[L_1(E)=\{w|w至少包含三个连续的0\}\]

\[L_2(E)=\{w|w以01结尾\}\]

\[L_3(E)=\{w|w的开头字符和结尾字符相同\}\]

\[L_4(E)=\{w|w由于交替的0和1组成\}\]

\[L_5(E)=\{w|w的第二位到第5位至少有一个1 \wedge |w|>2\}\]