正则表达式与正则语言

1、第三章正则表达式与正则语言13.1 正则表达式（Regular expression,RE） 两个语言L和M的连接，记作 ，定义为 则明显地， 两个语言L和M的并，记作 ，为集合并 语言类的运算：设L，M 为 上的语言，则 2语言L的Kleene闭包，记作 定义为 其中 归纳定义为 例如： 为 的Kleene闭包。 3.1 正则表达式（Regular expression,RE）3正则表达式（递归定义）：（1） 是 上的正则表达式，它表示语言 ，即 。（2） 是 上的正则表达式，它表示语言 ，即 。 3.1 正则表达式（Regular expression,RE）的语言 ：定义 设是一个字母表

2、，上的正则表达式E与所代表（3） ，是 正则表达式，它表示语言 。 4（4）如果E和F分别是 上的正则表达式，则表示的语言为L(E) 和L(F)，E和F的“和”（E+F)是 上的正则表达式且 L(E+F)=L(E)L(F)。E和F的“乘积”（EF）是 上的正则表达式且L(EF)=L(E)L(F)。E的克林闭包 是 上的正则表达式且 。（5）只有满足（1）（4）的表达式才是 上的正则表达式。3.1 正则表达式（Regular expression,RE）5例1.设 0是正则表达式，表示语言 。1是正则表达式，表示语言 。(0+1)是正则表达式，表示语言 。（01）是正则表达式，表示语言 。 是正

3、则表达式，表示所有以01结尾的字符串组成的语言。3.1 正则表达式（Regular expression,RE）6例2.写一个表达式，它表示了交替0和1的串的集合。例如：1010101，010101 等等3.1 正则表达式（Regular expression,RE）7正则表达式的运算优先级规定如下：1）星运算符有最高优先级；2）下一个运算级是连接运算符（乘积）；3）并（和）是最低级。例如：3.1 正则表达式（Regular expression,RE）83.2 有穷自动机和正则表达式 已证明DFA,NFA, 识别的语言类是一致的，下面进一步证明它们和正则表达式的语言也是一致的。定理3.4 如

4、果对于某个DFA A, L=L(A)，则存在一个正则表达式R,使得L=L(R)。 证明 设DFA 令 93.2 有穷自动机和正则表达式 即 是所有那些将DFA从给定状态 引导到状态 ，并且“途中”不经过（进入并离开）下标大于k的状态的所有字符串。但i,j不受k的限制。 这样 是所有可以将DFA从状态 引导到状态 的字符串的集合。这时 可递归定义为：103.2 有穷自动机和正则表达式 可证11假设存在从i到j的路径不经过比k高的状态，有类似情形3.2 有穷自动机和正则表达式 123.2 有穷自动机和正则表达式 从而 表示某个正则表达式的语言，因为 是正则表达式且 是由递归定义方法进行定义的。 明

5、显地 有正则表达式 ，递归定义！ 从而 可以用正则表达式表示出来。 ，（假设状态1是初始状态）133.2 有穷自动机和正则表达式 例1 给出这个自动机语言的正则表达式，求正则表达式 即可143.2 有穷自动机和正则表达式 而而153.2 有穷自动机和正则表达式 定理3.7 每一个用正则表达式来定义的语言都可以用有穷自动机来定义。证明 根据正则表达式与其表示的语言的定义，我们递归地来证明这个定理。（1） 空语言可以被下面的自动机接受 163.2 有穷自动机和正则表达式 （2） 可以被下面的自动机接受 173.2 有穷自动机和正则表达式 （3） 可以被下面的自动机接受 递归地，设E、F为两个正则表

6、达式，L(E)，L(F)可以被自动机 与 接受，下面证明 ， 与 也能被有穷自动机接受。 183.2 有穷自动机和正则表达式 . 能被下面的自动机接受 193.2 有穷自动机和正则表达式 . 可以被如下的自动机接受 203.2 有穷自动机和正则表达式 . 可以被如下的自动机接受 213.2 有穷自动机和正则表达式 例2 求表达式 的 0+1：010:1:223.2 有穷自动机和正则表达式 233.2 有穷自动机和正则表达式 24一些讨论： 3.2 有穷自动机和正则表达式 定理3.4把DFA转化成正则表达式的方法总是成立的，但代价太高：对于一个n状态的自动机，不仅要构造大约 个表达式，而且如果不

7、化简表达式，则在n个归纳步骤的每一步，表达式的长度平均增加到4倍。因此，这些表达式本身可能达到 个符号的长度级别。有一种通过消除状态把 DFA 转化为正则表达式的方法，在某些地方避免了重复工作。例如，在定理3.4的构造中，所有带上标 的表达式都利用同一个子表达式 ；因此写这个表达式的工作重复了 次。253.4 正则表达式的代数定律设E，F，G为 上的正则表达式，则 （1）结合律： （2）交换律：E+F=F+E （3）分配律：设E和F为 的两个正则表达式，若 ，则称E和F等价，也记做E=F。 下面讨论正则表达式的一些基本代数定律。263.4 正则表达式的代数定律(4) 幂等律：E+E=E(5) 加法运算零元素：(6) 乘法运算单位元：(7) 乘法运算零元素： (8)(9)(10)273.4 正则表达式的代数定律（11）我们证明（11）即证：也即：设 ，则 ，其中 ，从而 或 ，这样 或 ，因此 283.4 正则表达式的代数定律反之，明显地， 293.4 正则表达式的代数定律证明： ， r，s 为正则表达式， 若 ，则 为唯一解。 练习题30本章小结正则表达式 ： 这种代数记号恰好与有穷自动机描述相同的语言：正则语言。正则表达式运算符是：并、连接（或“点”）和闭包（或“星”）。正则表达式与有穷自动机的等价性：用归纳构造把 转化成正则表达式，其中构造出一些表达式作为路径标记，这些路