《形式语言与自动机正则表达式幻灯片.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机正则表达式幻灯片.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、形式语言与自动机 正则表达式第1页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 正则表达式n n6.1 引例n n6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题n n6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)(1)首先说明如何把首先说明如何把DFADFA转换成转换成GNFAGNFA(2)(2)说明如何把说明如何把GNFAGNFA转换成正则表达式转换成正则表达式第2页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 1：算术表达式：(5+4)2,值为值为18，是一个
2、数字正则表达式：(0(01)0*,1)0*,正则表达式的值是一个语言正则表达式的值是一个语言n n注意：注意：注意：注意：n n(0(01)0*1)0*表示的是表示的是0101后加任意多个后加任意多个0 0构成的字符串所组成的语构成的字符串所组成的语言言n n0 0和和1 1是集合是集合00和和11的缩写，就是的缩写，就是001,1,这部分的值是语这部分的值是语言言0,10,1n n0*0*就是就是0*,0*,其值为所有包含任意个其值为所有包含任意个0 0的字符串构成的语言的字符串构成的语言n n在正则表达式中省略了连结运算符号在正则表达式中省略了连结运算符号o o,(0,(01)0*1)0*
3、实际上是实际上是(0(01)1)o o0*0*n n正则表达式可以用来描述满足正则表达式可以用来描述满足“某种模式某种模式”的字符串。的字符串。第3页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 很多应用程序及现代程序设计语言、文本编辑程很多应用程序及现代程序设计语言、文本编辑程序都提供用正则表达式描述模式的手段。序都提供用正则表达式描述模式的手段。n n例题例题例题例题2 2：正则表达式(0(01)*1)*n n其值为：由其值为：由0和和1 1的所有字符串组成的语言，也表示的所有字符串组成的语言，也表示为为0,1*n n表示方法表示方法表示方法表示方法：
4、记：记 为字母表，为字母表，也可以表示该字母表也可以表示该字母表中所有长度为中所有长度为1的字符串，而的字符串，而*为由该字母表中所为由该字母表中所有字符串组成的语言。有字符串组成的语言。n n如：如：(0*)*)(*1)表示所有以表示所有以0 0开头而以1 1结尾的字符串n n正则运算的优先级正则运算的优先级正则运算的优先级正则运算的优先级：先星号，后连结，最后并，要改变这种惯常的顺序需要用括号。第4页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 正则表达式n n6.1 引例n n6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题n n6.3
5、 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)(1)首先说明如何把首先说明如何把DFADFA转换成转换成GNFAGNFA(2)(2)说明如何把说明如何把GNFAGNFA转换成正则表达式转换成正则表达式第5页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 称R是一个正则表达式，如果R是n na,这里a是字母表中的一个元素；n n；n n；n n(R1R2)，这里R1和R2是正则表达式；n n(R1oR2)，这里R1和R2是正则表达式；n n(R1*)，这里R1是正则表达式；第6页，共35页，编辑于2022年，星期六9/22/2
6、022 1:35 PMhttp:/ n在在(1)(1)和和(2)(2)中，中，a a和 分别表示 a a 和和n n在在(3)(3)条中，条中，表示空语言表示空语言n n在第在第(4)(4)、(5)(5)、(6)(6)表示通过正则运算并、连结和星号表示通过正则运算并、连结和星号获得正则表达式获得正则表达式n n（用较小的正则表达式定义较大的正则表达式，是（用较小的正则表达式定义较大的正则表达式，是归纳定义归纳定义归纳定义归纳定义中的归纳中的归纳步骤）步骤）n n此处此处和和的区别：有一个空语句的语言，和空语言的区别：有一个空语句的语言，和空语言n n要想明显的区分正则表达式要想明显的区分正则表
7、达式R R和它所表示的语言时，和它所表示的语言时，后者用后者用L(R)L(R)表示。表示。第7页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 正则表达式n n6.1 引例n n6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题n n6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)(1)首先说明如何把首先说明如何把DFADFA转换成转换成GNFAGNFA(2)(2)说明如何把说明如何把GNFAGNFA转换成正则表达式转换成正则表达式第8页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMh
8、ttp:/ 1:35 PMhttp:/ 4：设设R R是任意的正则表达式，有下述恒等式成立。是任意的正则表达式，有下述恒等式成立。几个正则表达式的几个正则表达式的恒等式恒等式这些恒等式有助于对正则表达这些恒等式有助于对正则表达式定义的理解式定义的理解R=R空语言加上任何一个语言不改变这个语言Ro=R空串加上任何一个字符串上不改变这个字符串但是但是：R不一定等于R，Ro不一定等于R第10页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ n例题例题例题例题5 5：程序设计语言中的基本单位称为单字，如变程序设计语言中的基本单位称为单字，如变量名和常量，这些东西可以
9、用正则表达式描述。量名和常量，这些东西可以用正则表达式描述。通常是包括小数部分和正负号的的数值常量可以描述成通常是包括小数部分和正负号的的数值常量可以描述成下述语言的一个成员：下述语言的一个成员：+,-,(DD*+,-,(DD*DD*.D*DD*.D*D*.DD*)D*.DD*)其中，其中，D D 0,1,2,90,1,2,9，则，则7272，3.14,+7.3.14,+7.和和 -.01-.01是该语是该语言的字符串。言的字符串。n n在编译中，只要程序设计语言中的单字的语法用正则表达式描述出来，自动系统能够生成词法分词法分词法分词法分析程序析程序析程序析程序。这是编译程序的一部分，用来在开
10、始阶。这是编译程序的一部分，用来在开始阶段处理输入程序。段处理输入程序。第11页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 正则表达式n n6.1 引例n n6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题n n6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)(1)首先说明如何把首先说明如何把DFADFA转换成转换成GNFAGNFA(2)(2)说明如何把说明如何把GNFAGNFA转换成正则表达式转换成正则表达式第12页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 1
11、:35 PMhttp:/ 正则表达式n n6.1 引例n n6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题n n6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)(1)首先说明如何把首先说明如何把DFADFA转换成转换成GNFAGNFA(2)(2)说明如何把说明如何把GNFAGNFA转换成正则表达式转换成正则表达式第14页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ n引理1 如果一个语言可以用正则表达式描述，则它是正则的。证明：证明：考虑正则表达式R定义的6种情况(1)R=a,这里a是字母表中的一个元素
12、，那么L(R)=a,下述NFA识别L(R)(注意：这台机器符合NFA的定义，但是不符合DFA的定义，因为(1)(2)形式的表示，N=(q1,q2,q1,q2),其中 的定义为(q1,a)=q2 (q1,b)=,若第15页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 1:35 PMhttp:/ n例题例题6：分若干阶段把正则表达式(aba)*转换成NFA，从最小的子表达式到大一点到大一点的子表达式逐步建立。使用构造证明中的方法一般不能给出状态最少的NFA。a和b (1)第17页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/
13、 ab (2)aba (3)第18页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 1:35 PMhttp:/ 正则表达式n n6.1 引例n n6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题n n6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)(1)首先说明如何把首先说明如何把DFADFA转换成转换成GNFAGNFA(2)(2)说明如何把说明如何把GNFAGNFA转换成正则表达式转换成正则表达式第20页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ n引理2 如果一个
14、语言是正则的，那么它可以用正则表达式描述。第21页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 正则表达式n n6.1 引例n n6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题n n6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)(1)首先说明如何把首先说明如何把DFADFA转换成转换成GNFAGNFA(2)(2)说明如何把说明如何把GNFAGNFA转换成正则表达式转换成正则表达式第22页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ n广义非确定型有穷自动机GNFA
15、第23页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ nGNFA其实就是NFA，只是转移箭头可以用任何正则表达式作标号，而不是只能用字母和做标号。n nGNFA读入输入符号段，而不必一次值读一个符号。n nGNFA是非确定性的，有几种不同的方式处理同一个符号串 第24页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ n起始状态有射到其他每一个状态的箭头，但是没有从其他任何状态射入的箭头n n有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到其他任何状态的箭头；n n除起始状态和接受状态外，每一个状态到
16、自身或其他状态都有一个箭头。第25页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 添加一个新的起始状态和一个新的接受状态；添加一个新的起始状态和一个新的接受状态；从新的起始状态到老的起始状态有一个从新的起始状态到老的起始状态有一个 箭头；箭头；从每一个老的接受状态到新接受状态有一个从每一个老的接受状态到新接受状态有一个 箭头；箭头；如果一个箭头有多个标记如果一个箭头有多个标记(即两个状态之间有多个方向即两个状态之间有多个方向相同的箭头相同的箭头)，则把它替换为一个标记着原先标记的，则把它替换为一个标记着原先标记的并集的箭头；并集的箭头；在没有箭头的状态之间
17、添加在没有箭头的状态之间添加 标记。标记。(此步骤不改变识此步骤不改变识别的语言，因为别的语言，因为 标记的箭头永远不能被使用标记的箭头永远不能被使用)第26页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 正则表达式n n6.1 引例n n6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题n n6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)(1)首先说明如何把首先说明如何把DFADFA转换成转换成GNFAGNFA(2)(2)说明如何把说明如何把GNFAGNFA转换成正则表达式转换成正则表达式第27页，共3
18、5页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ n每一个GNFA都有个状态(证明：证明：GNFAGNFA都有起始状态和接受状态，且是两个不同的状都有起始状态和接受状态，且是两个不同的状态态)n n每一个个状态的GNFA都可以转为为等价的状态的GNFA(如何转变才是本部分的关键所在如何转变才是本部分的关键所在)第28页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ n第二步：仅2个状态的GNFA，可以很容易的转换成为正则表达式n n证明：因为只有起始状态和接受状态两个状态，因此，只有一个从起始状态到接受状态的转移箭头，这个箭头上的
19、标记就是等价的正则表达式。n n解决这个关键环节解决这个关键环节：当k 2时，如何构造等价的少一个状态的GNFA第29页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ n基本思路：基本思路：任选一个不是起始状态和接受状态的中间任选一个不是起始状态和接受状态的中间状态，将其删除，记为状态，将其删除，记为q删除并通过修改留下来的部分，删除并通过修改留下来的部分，使其仍然识别相同的语言。使其仍然识别相同的语言。(这个q q删除一定能找到吗删除一定能找到吗？)n n 删除删除q q删除后，改动每一个留下来的箭头上标记的正则表达式。新标记中加入失去的计算，从而弥补由于删除来的损失。从状态qiqi到qj的新标记是描述使机器直接从从状态qiqi到到qjqj或通过状态或通过状态q q删除带到qjqj的所有字符串的表达式。图示给出了一个例子：第30页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/ 1:35 PMhttp:/ 1:35 PMhttp:/ 1:35 PMhttp:/ n习题习题：将下图中三个状态的DFA，转化为正则表达式。要求严格按照上述步骤进行。第34页，共35页，编辑于2022年，星期六9/22/2022 1:35 PMhttp:/