3.3.1-正规式.pptVIP

3.3 正规表达式和自动机 3.3.1 正规式和正规集 3.3.2 确定有限自动机 3.3.3 非确定有限自动机 3.3.4 正规文法与有限自动机的等价性 3.3.5 正规式与有限自动机的等价性 3.3.6 确定有限自动机的化简 3.3.1 正规式和正规集 ☆1、正规式的引入 ☆2、正规式和正规集的定义 ☆3、两个正规式等价的定义 ☆4、正规式服从的代数规律 1、正规式的引入 正规式、正规表达式、正则表达式 Regular Expression、RE 2 、正规式和正规集的定义 设字母表为Σ, 辅助字母表Σ’={ Φε | · * ( ) } (3)假定U和V都是Σ上的正规式， 他们所表示的正规集分别为L(U)和L(V) (4)仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式表示的字集才是Σ上的正规集 规定算符的优先顺序 ( ) * · | 令∑={a，b}，∑上的正规式和相应的正规集 正规式 a b a|b ab (a|b)(a|b) a* (a|b)* 正规集 {a} {b} {a, b} {ab} {aa, ab, ba, bb} {ε, a, aa, aaa, …} {ε, a, b, aa, ab …所有由a或b组成的串} 例 3.1 ∑={a，b} P47 ba* {b}{a}* Σ上所有以b为首,后面跟任意多个a的符号串 a(a|b)* {a}{a,b}* Σ上所有以a为首的符号串 (a|b)*(aa|bb)(a|b)* {a,b}*{aa,bb}{a,b}* Σ上所有含有两个相继a或两个相继b的符号串 例 3.2 ∑={A,B,0,1} P47 (A|B)(A|B|0|1)* {A,B}{A,B,0,1}* ∑上 ‘标识符’的全体 (0|1)(0|1)* {0,1}{0,1}* ∑上 ‘数’的全体 补充例: ∑={0,…,9,a,…z,A,…Z} 正规式 d = 0|1|…|9 正规式 l = a|…|z|A|…|Z 整数的集合: dd* (dd* = d+) 标识符的集合: l(l|d)* 3、两个正规式等价的定义 若两个正规式U和V表示的正规集相同, 则说U和V等价，写作U=V 例 a|b = b|a b(ab)* = (ba)* b (a|b)* = (a* |b* )* 4、正规式服从的代数规律 U,V,W为正规式 ① U|V=V|U ② U|(V|W)=(U|V)| W ③ (UV)W=U(VW) ④ U(V|W)=UV|UW ， (V|W)U=VU|WU ⑤ εU=Uε=U 补充：正规式服从的代数规律 r为正规式 ⑥ r|r=r (r*)* = r* r*=ε|r|rr|… ∑*=∑0 ?∑1 ?∑2 … ? ∑n ? … 课堂练习 r,s是正规式, 证明 (rs)*r = r(sr)* 补充例：定义无符号数的正规式 2，12.59，3.6e2，471.88e-1 Σ = {d . e + -} d为0~9的数字, ‘.’表示小数点 d* (.dd*|ε) (e(+|-|ε)dd* |ε) 课堂练习 ?＝{a,b}，写出描述以下集合的正规式 不以a开头, 但以aa结尾的字符串集合 L={ a2n+1b2ma2p+1|n≥0,m≥1, p≥0} * YTU 正规式 正规集 正规文法 正规语言 正规语言是VT*上的正规集 L(G)? VT* 单词描述工具 {ε} ε { } Φ {a} a∈Σ 正规集 正规式 (1) (2) Σ: 语言的字母表 VT (L(U))* (U)* 闭包 补充: ( ) 连接积 或 L(U)∪L(V) U|V L(U)·L(V) U·V L(U) (U) 正规集 正规式 补充例 ?