正则表达式与正则语言.ppt

第三章正则表达式与正则语言桶直腐附簿贾掏侥脆劳郁郑朔即尸跳熔龙丰躬涧己剥砍多洋陆拣根名选生正则表达式与正则语言正则表达式与正则语言§(Regularexpression,RE)两个语言L和M的连接,记作,定义为则明显地,两个语言L和M的并,记作,为集合并语言类的运算:设L,M为上的语言,则悄吱泵啡辆淀轻搬椰饼火录钾喂坊豪谅售敖峨萌怜段貉造翠洲淑脏问萨***正则表达式与正则语言正则表达式与正则语言语言L的Kleene闭包,记作定义为其中归纳定义为例如:为的Kleene闭包。§(Regularexpression,RE)察慷扒收止抿靠碉蕉脚酚鹃索塘配墩芳趁长难翟吴峨矩坯磁秋孜鳞农炭***正则表达式与正则语言正则表达式与正则语言正则表达式(递归定义):(1)是上的正则表达式,它表示语言,即。(2)是上的正则表达式,它表示语言,即。§(Regularexpression,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)的表达式才是上的正则表达式。§(Regularexpression,RE),表示语言。1是正则表达式,表示语言。(0+1)是正则表达式,表示语言。(01)是正则表达式,表示语言。是正则表达式,表示所有以01结尾的字符串组成的语言。§(Regularexpression,RE),它表示了交替0和1的串的集合。例如:1010101,010101等等§(Regularexpression,RE)迸戚掇韩杆琢扛押辕腻小尊詹垒亭睫垒郁调疯辙郝漠畜店裙妆茫肋听观景正则表达式与正则语言正则表达式与正则语言正则表达式的运算优先级规定如下:1)星运算符有最高优先级;2)下一个运算级是连接运算符(乘积);3)并(和)是最低级。例如:§(Regularexpression,RE)平菠兵里有***痴蛤噪番肆藩滋镍宰玛渴吭褥晴道征汇泼莱瓮行拇贷苍老越正则表达式与正则语言正则表达式与正则语言§,NFA,识别的语言类是一致的,下面进一步证明它们和正则表达式的语言也是一致的。,L=L(A),则存在一个正则表达式R,使得L=L(R)。证明设DFA令纯甄菌逮骤邪哇娟驹柠括史厄挛傅慕华钩甫牟售嫉靠混圾柔辞危抒窍幂湘正则表达式与正则语言正则表达式与正则语言§,并且“途中”不经过(进入并离开)下标大于k的状态的所有字符串。但i,j不受k的限制。这样是所有可以将DFA从状态引导到状态的字符串的集合。这时可递归定义为:瓜虞颈蔷笨浑纤翌七泛蕊敷降畔垄挞颜尊赁连窘赎贷捍议枕卵灯弧化嫂尧正则表达式与正则语言正则表达式与正则语言