3.2.2正规式和正规集p52-53 对于字母表∑，正规式和正规集的递归定义为： 说明 正规式r 正规集L(r) 1.是空符号 8,0 {e},⑦ 2.若a∈∑ a {a} 3.若u,v是正规 uV(或) L(u)UL(v) 式对应正规集 u.V(连接) L(u)L(v) 是L(u),L(v) u*(闭包) L(u)* 4.仅由有限次使用上述三步骤而得到的表达式才是Σ上 的正规式，仅由这些正规式所表示的字集才是∑上的正 规集 25.4.3
25.4.3 11 3.2.2正规式和正规集 p52-53 对于字母表∑，正规式和正规集的递归定义为： 说明 正规式 r 正规集L(r) 1. ∅是空符号 ε,∅ {ε}, ∅ 2.若a∈∑ a {a} 4.仅由有限次使用上述三步骤而得到的表达式才是∑上 的正规式，仅由这些正规式所表示的字集才是∑上的正 规集 u|v(或) L(u)∪L(v) u ● v (连接) L(u)L(v) u* (闭包) L(u)* 3.若u,v是正规 式对应正规集 是 L(u),L(v)
正规式和正规集举例 © 设Σ={0,1} 正规式 正规集 0 {0} 1 {1) 01 {0}U1} {0,1} 01 {0}{1} {01} 10 1}{0} {10} 0* {0}* {e,0,00,000,.} 1* {1}* {e,1,11,111,. 25.4.3 ☒22
25.4.3 12 正规式和正规集举例 设 ∑={0,1} 正规式 正规集 0 {0} 1 {1} 0|1 {0}∪{1} {0,1} 01 {0}{1} {01} 10 {1}{0} {10} 0 * {0}* {ε,0,00,000,.} 1 * {1}* {ε,1,11,111,.}
正规式和正规集举例p45例3.2 0 设Σ={a,b} 正规式 正规集 a {a} a b {a,b} ab {ab} (a b)*{a,b}*{e,a,b,aa,ab,ba,bb,aaa,. 所有由a,b组成的串} 25.4.3 国23
25.4.3 13 正规式和正规集举例 p45 例3.2 设 ∑={a，b} 正规式 正规集 a {a} a|b {a,b} ab {ab} (a|b) * {a,b} * {ε,a,b,aa,ab,ba,bb,aaa,., 所有由a,b组成的串}
正规式和正规集举例p45例3.2 o设∑={a,b} 正规式 正规集 ba* ∑上所有以b为首后跟任意多个a的字 a(ab)*∑上所有以a为首的字 (a b)*(aa bb)(a b)* ∑上所有含有两个相继的a或两个相继的b的字 0设∑={A,B,0,1} 正规式 正规集 (A|B)(AB01)*∑上的“标识符”的全体 (01)(01)*∑上的“数”的全体 25.4.3 ☒214
25.4.3 14 正规式和正规集举例 p45 例3.2 设 ∑={a，b} 正规式 正规集 ba* ∑上所有以b为首后跟任意多个a的字 a(a|b) * ∑上所有以a为首的字 (a|b) *(aa|bb)(a|b) * ∑上所有含有两个相继的a或两个相继的b的字 设∑={A,B,0,1} 正规式 正规集 (A|B)(A|B|0|1)* ∑上的“标识符”的全体 (0|1)(0|1)* ∑上的“数”的全体
正规式运算符的优先级p53 0 米 高于. 高于」，具有结合律、分配律，可省略 ▣|具有交换律、结合律 ▣（)指定优先关系 口正规式的性质，设U、V和W均为正规式，则 oUV=VU(交换律) oU(WW)=(UV)|W(结合律) oU(VW)=(UV)W(结合律) oU(VW)=UVUW(VW)U=VUU(分配律) e U=Ue=U 25.4.3 国215
25.4.3 15 正规式运算符的优先级 p53 * 高于 . . 高于|，具有结合律、分配律,可省略 | 具有交换律、结合律 ( )指定优先关系 正规式的性质,设U、V和W均为正规式,则 U|V=V|U (交换律) U|(V|W)=(U|V)|W (结合律) U(VW)=(UV)W (结合律) U(V|W)=UV|UW (V|W)U=VU|WU (分配律) εU=Uε=U