正则表达式的例子 Σ={a,b} L(ab)=fa,bg L(ab(ab)=aa, ab, ba, bb) L(a)=s, a, aa, aaa, aaaa (ab )=e, a, b, aa, ab, ba, bb, aaa, aab L(aa b)=fa, b ab, aab, aaab,.)
正则表达式的例子 • Σ={a,b} • L(a|b) = {a,b} • L((a|b)(a|b)) = {aa,ab,ba,bb} • L(a*) = {ε,a,aa,aaa,aaaa,……} • L((a|b)*) = {ε,a,b,aa,ab,ba,bb, aaa,aab,……} • L(a|a*b) = {a,b,ab,aab,aaab,…}
正则集合、等价 如果L()L(s),正则表达式和S等价。 定律 描述 rIs=sr 是可以交换的 r|(s{t)=(r|)|t 是可结合的 r(st)=(rst 连接是可结合的 r(8t)=r8rt;(8t)r=8rtr连接对是可分配的 eT三TE〓T 是连接的单位元 r*=(rle 闭包中一定包含E T T *具有幂等性 图3-7正则表达式的代数定律
正则集合、等价 • 如果L(r)=L(s)，正则表达式r和s等价
正则定义(1) 为了书写方便,可以给正则表达式命名,且可 以通过名字使用正则表达式 正则定义是如下形式的定义序列 d1→ d y dn→ 其中 d不在∑中,且各不相同 每个是字母表∑U{d1d2,d41}上的正则表达式。 这保证了不会出现递归定义
正则定义（1） • 为了书写方便，可以给正则表达式命名，且可 以通过名字使用正则表达式 • 正则定义是如下形式的定义序列 d1 → r1 d2 → r2 … … dn→rn • 其中： – di不在Σ中，且各不相同 – 每个ri是字母表Σ U {d1 ,d2 ,…,di-1}上的正则表达式。 这保证了不会出现递归定义
正则定义(2) 各个d的∑上的正则表达式如下: d的正则表、剑1° 将I中的d;替换为r,得到d的正则表达式。 将中的d1,d2,d1替换为各自的正则表达式, 得到d的正则表达式。 注意:替换的时候不能破坏替换进去的d!的 完整性
正则定义（2） • 各个di的Σ上的正则表达式如下： – d1的正则表达式即r1。 – 将r2中的d1替换为r1，得到d2的正则表达式。 – … … … … – 将ri中的d1 ,d2 ,…,di-1替换为各自的正则表达式， 得到di的正则表达式。 • 注意：替换的时候不能破坏替换进去的di的 完整性
正则定义的例子 C语言标识符的正则定义 -letter > AB.Zab.z digit0|1|….9 id letter (letter digit ) id对应的正则表达式为 -(A|B|….|Z|ab|….|z)(A|B|…|Z|ab 1….z|_)(0|11….19)*
正则定义的例子 • C语言标识符的正则定义 – letter_ → A | B | … | Z | a | b | … | z | _ – digit → 0 | 1 | … | 9 – id → letter_ ( letter_ | digit )* • id对应的正则表达式为 – (A | B | … | Z | a | b | … | z | _) ((A | B | … | Z | a | b | … | z | _) |(0 | 1 | … | 9))*