3.3.2正规式和正规集p45-46 对于字母表∑，正规式和正规集的递归定义为： 说明 正规式r 正规集L(r) 1.∧是空符号 e, {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.2 ☒26
25.4.2 6 3.3.2 正规式和正规集 p45-46 对于字母表∑，正规式和正规集的递归定义为： 说明 正规式 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)
正规式和正规集举例D45例3.2 0 设∑={a,b} 正规式 正规集 a {a} a b {a}U[b}{a,b} ab {a}{b}{ab} a* {a}*{e,a,aa,aaa,.} (a b)*{a,b)*{s,a,b,aa,ab,ba,bb,aaa,. 所有由a,b组成的串} 25.4.2 27
25.4.2 7 正规式和正规集举例 p45 例3.2 设 ∑={a，b} 正规式 正规集 a {a} a|b {a}∪{b}{a,b} ab {a}{b} {ab} a * {a}* {ε,a,aa,aaa,.} (a|b) * {a,b} * {ε,a,b,aa,ab,ba,bb,aaa,., 所有由a,b组成的串}
正规式和正规集举例p45例3.2 o设∑={a,b} 正规式 正规集 ba* Σ上所有以b为首后跟任意多个a的字 a(a b)* Σ上所有以a为首的字 (a b)*(aa bb)(a b)* ∑上所有含有两个相继的a或两个相继的b的字 设∑={A,B,0,1 正规式 正规集 (AB)(AB01)* ∑上的“标识符”的全体 (01)(01)* ∑上的“数”的全体 25.4.2 ☒28
25.4.2 8 正规式和正规集举例 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)* ∑上的“数”的全体
正规式运算符的优先级p45 高于 口·高于，具有结合律、分配律，可省略 ▣具有交换律、结合律 ()指定优先关系 口正规式的性质，设U、V和W均为正规式，则 or|s=sr(交换律) or|(st)=(rs)|t(结合律) ▣(rs)t=r(st)(结合律) or(st)=rsrt(st)r=sr|tr(分配律) 口er=r,re=r（恒等率) orr=r(抽取率) 25.4.2 ☒D9
25.4.2 9 正规式运算符的优先级 p45 * 高于 . . 高于|，具有结合律、分配律,可省略 | 具有交换律、结合律 ( )指定优先关系 正规式的性质,设U、V和W均为正规式,则 r|s=s|r (交换律) r|(s|t)=(r|s)|t (结合律) (rs)t=r(st)(结合律) r(s|t)=rs|rt (s|t)r=sr|tr (分配律) εr=r,rε=r（恒等率） r|r=r（抽取率）
正规式的等价性p45 口一个正规式r表示的正规集也就是r 所定义的语言，记为L(r) 0 若两个正规式r和s所表示的正规集 L(r)=L(s),则称r,s等价 记作r=S 例如：1(01)*=(10)*1 (a b)=b a {1,101,10101,.} (ab)*=(a*b*)* 25.4.2 ☒210
25.4.2 10 正规式的等价性 p45 一个正规式 r 表示的正规集也就是 r 所定义的语言，记为 L(r) 若两个正规式r和s所表示的正规集 L(r)=L(s),则称r,s等价 记作 r = s 例如：1(01) *=(10) *1 {1,101,10101,.} (a|b)=b|a (a|b)*=(a*|b*) *