形式语言与自动机-6-正则表达式.ppt

*/* (1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式*/*例题1::算术表达式:(5+4)×2,值为18,是一个数字正则表达式:(0∪1)0*,正则表达式的值是一个语言注意:(0∪1)0*表示的是01后加任意多个0构成的字符串所组成的语言0和1是集合{0}和{1}的缩写,就是{0}∪{1},这部分的值是语言{0,1}0*就是{0}*,其值为所有包含任意个0的字符串构成的语言在正则表达式中省略了连结运算符号o,(0∪1)0*实际上是(0∪1)o0*正则表达式可以用来描述满足“某种模式”的字符串。*/*很多应用程序及现代程序设计语言、文本编辑程序都提供用正则表达式描述模式的手段。例题2:正则表达式(0∪1)*其值为:由0和1的所有字符串组成的语言,也表示为{0,1}*表示方法:记∑为字母表,∑也可以表示该字母表中所有长度为1的字符串,而∑*为由该字母表中所有字符串组成的语言。如:(0∑*)∪(∑*1)表示所有以0开头而以1结尾的字符串正则运算的优先级:先星号,后连结,最后并,要改变这种惯常的顺序需要用括号。*/*定义称R是一个正则表达式,如果R是a,这里a是字母表∑中的一个元素;ε;φ;(R1∪R2),这里R1和R2是正则表达式;(R1oR2),这里R1和R2是正则表达式;(R1*),这里R1是正则表达式;*/*说明:在(1)和(2)中,a和ε分别表示{a}和{ε}在(3)条中,φ表示空语言在第(4)、(5)、(6)表示通过正则运算并、连结和星号获得正则表达式(用较小的正则表达式定义较大的正则表达式,是归纳定义中的归纳步骤)此处ε和φ的区别:有一个空语句的语言,和空语言要想明显的区分正则表达式R和它所表示的语言时,后者用L(R)表示。*/*例题3:在下面的句子中,字母表为{0,1}*/*例题4:设R是任意的正则表达式,有下述恒等式成立。*/*例题5:程序设计语言中的基本单位称为单字,如变量名和常量,这些东西可以用正则表达式描述。通常是包括小数部分和正负号的的数值常量可以描述成下述语言的一个成员:{+,--,ε}(DD*∪DD*.D*∪D*.DD*)其中,D={0,1,2,…,9},则72,,+-.01是该语言的字符串。在编译中,只要程序设计语言中的单字的语法用正则表达式描述出来,自动系统能够生成词法分析程序。这是编译程序的一部分,用来在开始阶段处理输入程序。