正则表达式与正则语言.ppt
第三章正则表达式与正则语言3.1 正则表达式（Regular expression,RE）两个语言L和M的连接，记作 ，定义为 则明显地，两个语言L和M的并，记作 ，为集合并 语言类的运算：设L，M 为 上的语言，则 语言L的Kleene闭包，记作 定义为 其中 归纳定义为 例如：为 的Kleene闭包。3.1 正则表达式（Regular expression,RE）正则表达式（递归定义）：（1）是 上的正则表达式，它表示语言 ，即 。（2）是 上的正则表达式，它表示语言 ，即 。3.1 正则表达式（Regular expression,RE）的语言 ：定义 设是一个字母表，上的正则表达式E与所代表（3），是 正则表达式，它表示语言 。（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）例1.设 0是正则表达式，表示语言 。1是正则表达式，表示语言 。(0+1)是正则表达式，表示语言 。（01）是正则表达式，表示语言 。是正则表达式，表示所有以01结尾的字符串组成的语言。3.1 正则表达式（Regular expression,RE）例2.写一个表达式，它表示了交替0和1的串的集合。例如：1010101，010101 等等3.1 正则表达式（Regular expression,RE）正则表达式的运算优先级规定如下：1）星运算符有最高优先级；2）下一个运算级是连接运算符（乘积）；3）并（和）是最低级。例如：3.1 正则表达式（Regular expression,RE）3.2 有穷自动机和正则表达式 已证明DFA,NFA,识别的语言类是一致的，下面进一步证明它们和正则表达式的语言也是一致的。定理3.4 如果对于某个DFA A,L=L(A)，则存在一个正则表达式R,使得L=L(R)。证明 设DFA 令 3.2 有穷自动机和正则表达式 即 是所有那些将DFA从给定状态 引导到状态 ，并且“途中”不经过（进入并离开）下标大于k的状态的所有字符串。但i,j不受k的限制。这样 是所有可以将DFA从状态 引导到状态 的字符串的集合。这时 可递归定义为：3.2 有穷自动机和正则表达式 可证假设存在从i到j的路径不经过比k高的状态，有类似情形3.2 有穷自动机和正则表达式 3.2 有穷自动机和正则表达式 从而 表示某个正则表达式的语言，因为 是正则表达式且 是由递归定义方法进行定义的。明显地 有正则表达式 ，递归定义！从而 可以用正则表达式表示出来。，（假设状态1是初始状态）3.2 有穷自动机和正则表达式 例1 给出这个自动机语言的正则表达式，求正则表达式 即可3.2 有穷自动机和正则表达式 而而3.2 有穷自动机和正则表达式 定理3.7 每一个用正则表达式来定义的语言都可以用有穷自动机来定义。证明 根据正则表达式与其表示的语言的定义，我们递归地来证明这个定理。（1）空语言可以被下面的自动机接受 3.2 有穷自动机和正则表达式（2）可以被下面的自动机接受 3.2 有穷自动机和正则表达式（3）可以被下面的自动机接受 递归地，设E、F为两个正则表达式，L(E)，L(F)可以被自动机 与 接受，下面证明 ，与 也能被有穷自动机接受。3.2 有穷自动机和正则表达式.能被下面的自动机接受 3.2 有穷自动机和正则表达式.可以被如下的自动机接受 3.2 有穷自动机和正则表达式.可以被如下的自动机接受 3.2 有穷自动机和正则表达式 例2 求表达式 的 0+1：010:1:3.2 有穷自动机和正则表达式 3.2 有穷自动机和正则表达式 一些讨论：3.2 有穷自动机和正则表达式 定理3.4把DFA转化成正则表达式的方法总是成立的，但代价太高：对于一个n状态的自动机，不仅要构造大约 个表达式，而且如果不化简表达式，则在n个归纳步骤的每一步，表达式的长度平均增加到4倍。因此，这些表达式本身可能达到 个符号的长度级别。有一种通过消除状态把 DFA 转化为正则表达式的方法，在某些地方避免了重复工作。例如，在定理3.4的构造中，所有带上标 的表达式都利用同一个子表达式 ；因此写这个表达式的工作重复了 次。3.4 正则表达式的代数定律设E，F，G为 上的正则表达式，则（1）结合律：（2）交换律：E+F=F+E（3）分配律：设E和F为 的两个正则表达式，若 ，则称E和F等价，也记做E=F。下面讨论正则表达式的一些基本代数定律。3.4 正则表达式的代数定律(4)幂等律：E+E=E(5)加法运算零元素：(6)乘法运算单位元：(7)乘法运算零元素：(8)(9)(10)3.4 正则表达式的代数定律（11）我们证明（11）即证：也即：设 ，则 ，其中 ，从而 或 ，这样 或 ，因此 3.4 正则表达式的代数定律反之，明显地，3.4 正则表达式的代数定律证明：，r，s 为正则表达式，若 ，则 为唯一解。练习题本章小结正则表达式正则表达式 ：这种代数记号恰好与有穷自动机描述相同的语言：正则语言。正则表达式运算符是：并、连接（或“点”）和闭包（或“星”）。正则表达式与有穷自动机的等价性：正则表达式与有穷自动机的等价性：用归纳构造把 转化成正则表达式，其中构造出一些表达式作为路径标记，这些路径经过越来越大的状态集合。另一种方法是，用状态消除过程来构造DFA的正则表达式。反之，从正则表达式可以递归地构造出 。正则表达式代数正则表达式代数：正则表达式满足许多算术的代数定律，但有所不同。并和连接是结合的，但只有并是交换的。连接对于并是分配的。并是幂等的。
