编译原理（二）词法-1(正规表达式与有限自动机简介).pptVIP

2.3.1：正规表达式与正规集（正规式的运算） 连接运算： 字的连接：设“ab”和“aab”是两个字，则 ab·aab = abaab 正规式的连接：RS?=?{α β | α∈Rβ∈S} 例：A={ab，bc} ,B={ac,cb },则： AB ={abac,abcb,bcac,bccb} 正规式的幂运算：正规式自身的n次连接 并约定： R0 = {ε}。 2.3 正规表达式与优先自动机简介 Rn?=?RR…R　　 n个 AB≠BA 2.3.1：正规表达式与正规集（正规式的运算） 闭包运算： 集合R的闭包表示为R*,具体定义为： R*?=?R0∪R1∪R2∪R3∪… 集合R的正闭包表示为R+,具体定义为： R+ =?R1∪R2∪R3∪… = RR*? 显然： R*= R0∪R+ 2.3 正规表达式与优先自动机简介 2.3.1：正规表达式与正规集（正规式的运算性质） 对于Σ上的正规式R和S,如果它们的正规集满足L(R)=L(S), 则称R和S等价，记为R=S。正规式的性质有： (1)交换律： R | S = S | R (2)结合律： R | (S | T) = (R | S) | T；R(ST) = (RS)T (3)分配律： R(S | T) = RS | RT；(R | S)T?=?RT | ST (4)同一律： εR = Rε = R 2.3 正规表达式与优先自动机简介 2.3 课堂例题 例2.1 令Σ?=?{a,b}，设R?=?a(a | b)* 是Σ上的正规式，试求其表示的正规集。 [解答] L(R)?=?L(a(a | b)*)?=?L(a)L((a | b)*)?=?L(a)(L(a | b))*? =?L(a)(L(a)∪L(b))*　　? =?{a}({a}∪{b})*?=?{a}{a,b}*? =?{a}{ε, a, b, aa, ab, ba, bb, aaa, …}　　? =?{a, aa, ab, aaa, aab, aba, abb, aaaa, …}  2.3 课堂例题 例2.2 令Σ?=?{a,b}，根据给出的正规式，试描述其表示的正规集。 正规式 正规集 ba* ∑上所有的以b为首，并且后跟任意多个a 的字，{b, ba,baa,baaa,…} a(a|b)* ∑上所有的以a为首的字 (a|b)* (aa|bb) (a|b)* ∑上所有含有两个连续的a或者b的字 2.3 课堂例题 例2.3 判断下述正规式之间是否等价：　　(1) ?(a | b)*与a* | b* (2) (ab)*与a*b* [解答] (1) ? (a | b)* 对应的正规集其a、b可任意交替出现，如abbaaaba…；而 a* | b* 对应的正规集只可出现任意个a或者任意个b；因此两者不等价。　 [解答] (2) (ab)*对应的正规集是以任意个ab对出现的，即ababab…；而a*b*对应的正规集则是先出现任意个a后接任意个b，即a…ab…b；因此两者不等价。 2.3 课堂例题 例2.4 证明：设L (a+) = {a} *-{ε}, 则有a+ = aa *　　 [证明] L(a+) = {a} *-{ε} = {ε, a, a2, a3, …} -{ε} = {a, a2, a3, …} = {a}* {ε, a, a2, …} = {a}* {a} * = L(a) L(a*) = L(aa*) 故 a+ = aa* 2.4 正规表达式到有限自动机的构造 课后 2.4 正规式 (ab) * a 与正规式a (ba) * [解答] 格式参考上页PPT 第 2 讲 西北农林科技大学本科教程 主讲教师：赵建邦 第二章《词法分析》前三节 2.1 词法分析器的设计方法 2.2 一个简单的词法分析器 2.3 正规表达式与有限自动机简介