正则表达式与正则语言

第三章正则表达式与正则语言§3.1正则表达式（Regularexpression,RE）2两个语言L和M的连接，记作，定义为则明显地，LM,,|MyLxxyLMLL,而LLL1两个语言L和M的并，记作，为集合并ML语言类的运算：设L，M为上的语言，则**,ML,,,,110LLLLLLii3语言L的Kleene闭包，记作定义为其中归纳定义为nLLLLL210*nL*L例如：为的Kleene闭包。*,,,,,*naaaaa*§3.1正则表达式（Regularexpression,RE）正则表达式（递归定义）：（1）是上的正则表达式，它表示语言，即。()L（2）是上的正则表达式，它表示语言，即。)(L§3.1正则表达式（Regularexpression,RE）的语言：定义设是一个字母表，上的正则表达式E与所代表()LE（3），是正则表达式，它表示语言。aaaLa)(,a（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的克林闭包是上的正则表达式且。)(*E**)()(ELEL（5）只有满足（1）—（4）的表达式才是上的正则表达式。§3.1正则表达式（Regularexpression,RE）例1.设1,00是正则表达式，表示语言。01是正则表达式，表示语言。1(0+1)是正则表达式，表示语言。1,0（01）是正则表达式，表示语言。01是正则表达式，表示所有以01结尾的字符串组成的语言。1010*§3.1正则表达式（Regularexpression,RE）例2.写一个表达式，它表示了交替0和1的串的集合。例如：1010101，010101等等)0()01)(1(*§3.1正则表达式（Regularexpression,RE）正则表达式的运算优先级规定如下：1）星运算符有最高优先级；2）下一个运算级是连接运算符（乘积）；3）并（和）是最低级。例如：1011))1(0(**§3.1正则表达式（Regularexpression,RE）§3.2有穷自动机和正则表达式已证明DFA,NFA,识别的语言类是一致的，下面进一步证明它们和正则表达式的语言也是一致的。DFA定理3.4如果对于某个DFAA,L=L(A)，则存在一个正则表达式R,使得L=L(R)。证明设DFA令).,,,,,(121FqqqqAnklqyqywyyxwywqwqwRLlijikij，则，如果即的任意前缀而且对于),(,,,,),()(*)(§3.2有穷自动机和正则表达式即是所有那些将DFA从给定状态引导到状态，并且“途中”不经过（进入并离开）下标大于k的状态的所有字符串。但i,j不受k的限制。)()(kijRLiqjq这样是所有可以将DFA从状态引导到状态的字符串的集合。这时可递归定义为：)()(nijRLiqjq)()(kijRL§3.2有穷自动机和正则表达式jiqaqajiqaqaRLjijiij,),(,),()()0()()(,)(,)(,)(1)0(1)0()0()0(jiaaRaaRaRRkijkijijij可证)1()1(*)1()1()()(kijkkjkkkkikkijRRRRR假设存在从i到j的路径不经过比k高的状态，有类似情形1、○i~~~~○j，这条路线不经过状态k。在这种情况下，路径的标记属于的语言。2.路径经过状态k至少一次。路径分成几段，第1段不经过k从i到k，)1(kikR；○i~~~~○k~~~~○k~~~~○k~~~~○k~~~~○j最后一段不经过k从k到j，)1(kkjR；中间路径不经过k而从k到自身.)1(kkkR所有这种路径的标记的集合表示成正则表达式)1(*)1()1()1()(,kkjkkkkikkkkRRRR.(1)kijR§3.2有穷自动机和正则表达式§3.2有穷自动机和正则表达式从而表示某个正则表达式的语言，因为是正则表达式且是由递归定义方法进行定义的。明显地有正则表达式，递归定义！从而可以用正则表达式表示出来。)(kijRL)(kijR)(kijR)()()(1njFqRLALj)()(1njRL)(1njRLAL)(，（假设状态1是初始状态）§3.2有穷自动机和正则表达式例1给出这个自动机语言的正则表达式)()()2(12RLAL，求正则表达式即可)2(12R§3.2有穷自动机和正则表达式)1(22*)1(22)1(12)1(12)2(12)(RRRRR而)0(12*)0(11)0(11)0(12)1(12)(RRRRR)0(12*)0(11)0(21)0(22)1(22)(RRRRR而10,,0,1)0(22)0(21)0(12)0(11RRRR010)1)(1(0**)1(12R1010)1(22R*****)2(12)10(01)10()10(0101R§3.2有穷自动机和正则表达式定理3.7每一个用正则表达式来定义的语言都可以用有穷自动机来定义。证明根据正则表达式与其表示的语言的定义，我们递归地来证明这个定理。（1）空语言可以被下面的自动机接受)(L§3.2有穷自动机和正则表达式（2）可以被下面的自动机接受)(L§3.2有穷自动机和正则表达式（3）可以被下面的自动机接受aaL)(递归地，设E、F为两个正则表达式，L(E)，L(F)可以被自动机与接受，下面证明，与也能被有穷自动机接受。),,,,(AAAAFqQA),,,,(BBBBFqQB)()()(FLELFEL)()()(FLELEFL**)()(ELEL§3.2有穷自动机和正则表达式Ⅰ.能被下面的自动机接受)()(FLEL§3.2有穷自动机和正则表达式Ⅱ.可以被如下的自动机接受)()(FLEL§3.2有穷自动机和正则表达式Ⅲ.可以被如下的自动机接受*)(EL§3.2有穷自动机和正则表达式例2求表达式的)10(1)10(*NFA0+1：010:1:§3.2有穷自动机和正则表达式:)10(*§3.2有穷自动机和正则表达式:)10(1)10(*一些讨论：§3.2有穷自动机和正则表达式定理3.4把DFA转化成正则表达式的方法总是成立的，但代价太高：对于一个n状态的自动机，不仅要构造大约个表达式，而且如果不化简表达式，则在n个归纳步骤的每一步，表达式的长度平均增加到4倍。因此，这些表达式本身可能达到个符号的长度级别。3nn4有一种通过消除状态把DFA转化为正则表达式的方法，在某些地方避免了重复工作。例如，在定理3.4的构造中，所有带上标的表达式都利用同一个子表达式；因此写这个表达式的工作重复了次。k*)1(kkkR2n§3.4正则表达式的代数定律设E，F，G为上的正则表达式，则（1）结合律：)()(FGEGEF)()(GFEGFE（2）交换律：E+F=F+E（3）分配律：GEFEEGFEGEFGFE)()(设E和F为的两个正则表达式，若，则称E和F等价，也记做E=F。下面讨论正则表达式的一些基本代数定律。)()(FLEL§3.4正则表达式的代数定律(4)幂等律：E+E=E(5)加法运算零元素：EE(6)乘法运算单位元：EEE(7)乘法运算零元素：EE(8)**,(9)**)(EE(10)******,EEEEE§3.4正则表达式的代数定律（11）****FEFE我们证明（11）即证：))(())((****FELFEL也即：****))()(())()((FLELFLEL设，则，其中*))()((FLELwn21)()(FLELwi，从而或，这样或)(ELwi)(FLwi**)()(FLELwwii**)()(FLELwwii，因此***))()((FLELw****)()()()(FLELFLEL§3.4正则表达式的代数定律反之，)()()(),()()(FLELFLFLELEL明显地，**)()()(FLELEL**)()()(FLELFL*****))()(()()()()()()(FLELFLELFLELFLEL****)()()()(FLELFLEL****))()(())()((FLELFLEL§3.4正则表达式的代数定律证明：，r，s为正则表达式，若，则为唯一解。sXrXr*srX练习题本章小结正则表达式：这种代数记号恰好与有穷自动机描述相同的语言：正则语言。正则表达式运算符是：并、连接（或“点”）和闭包（或“星”）。正则表达式与有穷自动机的等价性：用归纳构造把转化成正则表达式，其中构造出一些表达式作为路径标记，这些路径经过越来越大的状态集合。另一种方法是，用状态消除过程来构造DFA的正则表达式。反之，从正则表达式可以递归地构造出。NFADFA正则表达式代数：正则表达式满足许多算术的代数定律，但有所不同。并和连接是结合的，但只有并是交换的。连接对于并是分配的。并是幂等的。