第04章 正则表达式.ppt

* 有穷自动机--正则表达式 例4.6 给出一个由图4.2表示的DFA M，按照定理4.2中的方法，构造一个正则表达式代表L(M)。 对于所有的i和j,以及k=0,1,2, rkij的值列在图4.3中。其中某些正则表达式已被化简。例如，根据定理4.2中的（4-1）式，r122 = r021(r011)* r012 + r022 = 0(ε)*0+ε,显然可以化简为00+ε。又例如，r213= r112（r122）* r123 + r113 =0(ε+ 00)*(1+01)+1,由于(ε+ 00)*可以化简成(00)*，(1+01)可以写成(ε+0)1，我们可以有r213=0(00)*(ε+0)1+1。更进一步，由于(00)*(ε+0)可以化简为0*，于是r213可以化简为00*1+1，最后化简为0*1。 * 有穷自动机--正则表达式 图4.2中DFA的rkij表 k=0 k=1 k=2 rk11 rk12 rk13 rk21 rk22 rk23 rk31 rk32 rk33 ε 0 1 0 ε 1 Φ 0+1 ε ε 0 1 0 ε+00 1+01 Φ 0+1 ε (00)* 0(00)* 0*1 0(00)* (00)* 0*1 (0+1)(00)*0 (0+1)(00)* ε+(0+1)0*1 问题：每次计算需要构造n3个rkij， 每次迭代时rkij长度增长4n * 有穷自动机--正则表达式 状态消除法（构造GNFA,Generalized-NFA） 相对每一个终结状态q,都消除中间状态，只保留q0 . * 有穷自动机--正则表达式 对于每一个 ,通过上述的状态消除法，会得到以下： 或者 * 有穷自动机--正则表达式 示例 转成GNFA 消除状态B * 有穷自动机--正则表达式 示例 * 正则表达式的等价变换 +操作的交换律: R+S = S+R。因为：R+S代表集合L(R)∪L(S),而S+R代表集合L(S)∪L(R)，集合的并运算是满足交换律的; +操作的结合律: (R+S)+T = R+(S+T)； “连接”构造的结合律： (RS)T = R(ST)。 “连接”构造不满足交换律： 对于一般的正则表达式R和S，不能写RS = SR。 反例，如：R=1,S=0,它们分别代表集合{1}和{0}，RS代表集合{10}，而SR代表集合{01}，显然这两个集合是不相等的。 * 正则表达式的化简： φ+R = R+φ = R。根据正则表达式与它们所代表的集合的对应关系，等式正确; φ是构造符“+”的单位元。 εR = Rε = R。ε是连接构造的单位元。 φR = Rφ=φ。代表集合{}L(R)或L(R){}，任何集合与空集的连接结果都是空集。这就说明φ是连接构造的零元。 R(S+T)=RS+RT。 这一条称为“连接”对于“+”的左分配律。 (S+T)R=SR+TR。 这一条称为“连接”对于“+”的右分配律。 (R*)* = R* ； φ* =ε； ε* =ε； 扩充定义R+：代表集合：L(R)+ 。定律：①ε+ R+ = R* ，② R+ = RR* * 发现正则表达式定律的一般方法 考虑一条所谓的定律：(R+S)* =(R* S*)* 这里R，S是任意两个正则表达式。 一般方法：将每个变量都当做一个不同的符号，即可将任何带变量的一般的正则表达式都看做一个具体的正则表达式，即一个没有变量的正则表达式。 例如，把表达式(R+S)*中的变量R和S分别换成符号a和b,就得出正则表达式(a+b)*。而这个正则表达式所代表的语言L((a+b)*)，显然是字符a和b组成的一切串的集合。另一方面，把表达式(R* S*)*的变量R和S也分别换成符号a和b, 就得出正则表达式(a* b*)*。而这个正则表达式所代表的语言L((a* b*)*)，显然也是字符a和b组成的一切串的集合。左右相等成立。 定理 4.4 设E是带有变量V1，V2，…Vm 的正则表达式，通过把Vi的每次出现，都换成符号ai（i=1，2，…,m）得到具体的表达式C。则从每个属于L(C)的串a1a2…ak出发，把每个符号ai（1≤i≤k）都换成对应语言L(Vi)，就构造出L(E)。 * 1.4 正则表达式的应用 UNIX中的正则表达式 词法分析 查找文本中的模式 ...... * UNIX中的正则表达式 对正则表达式记号的第一项扩展是：大多数实际应用都处理ASCⅡ字符集，这是比较大的字母表。如果有一种需要在表达式中把所有字符都列出来，书写起来就非常不方便。因此，UNIX中的正则表达式允许书写字符类来尽可能紧凑地表示大的字符集。字符类的规则是： ①