形式语言与自动机 正则表达式

形式语言与自动机正则表达式第1页，共35页，2023年，2月20日，星期六4/21/202312:32AM/2第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式第2页，共35页，2023年，2月20日，星期六4/21/202312:32AM/3例题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*正则表达式可以用来描述满足“某种模式”的字符串。第3页，共35页，2023年，2月20日，星期六4/21/202312:32AM/4

很多应用程序及现代程序设计语言、文本编辑程序都提供用正则表达式描述模式的手段。例题2：正则表达式(0∪1)*其值为：由0和1的所有字符串组成的语言，也表示为{0,1}*表示方法：记∑为字母表，∑也可以表示该字母表中所有长度为1的字符串，而∑*为由该字母表中所有字符串组成的语言。如：(0∑*)∪(∑*1)表示所有以0开头而以1结尾的字符串正则运算的优先级：先星号，后连结，最后并，要改变这种惯常的顺序需要用括号。第4页，共35页，2023年，2月20日，星期六4/21/202312:32AM/5第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式第5页，共35页，2023年，2月20日，星期六4/21/202312:32AM/6定义称R是一个正则表达式，如果R是a,这里a是字母表∑中的一个元素；ε；φ；(R1∪R2)，这里R1和R2是正则表达式；(R1oR2)，这里R1和R2是正则表达式；(R1*)，这里R1是正则表达式；第6页，共35页，2023年，2月20日，星期六4/21/202312:32AM/7说明：在(1)和(2)中，a和ε分别表示{a}和{ε}在(3)条中，φ表示空语言在第(4)、(5)、(6)表示通过正则运算并、连结和星号获得正则表达式（用较小的正则表达式定义较大的正则表达式，是归纳定义中的归纳步骤）此处ε和φ的区别：有一个空语句的语言，和空语言要想明显的区分正则表达式R和它所表示的语言时，后者用L(R)表示。第7页，共35页，2023年，2月20日，星期六4/21/202312:32AM/8第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题

6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式第8页，共35页，2023年，2月20日，星期六4/21/202312:32AM/9例题3：在下面的句子中，字母表为{0,1}0*10*{ω|ω恰好有一个1}∑*1∑*{ω|ω至少有一个1}∑*001∑*{ω|ω中含有子串001}(∑∑)*{ω|ω是偶长度的字符串}(∑∑∑)*{ω|ω是长度为3的字符串}01∪10{01,10}0∑*0∪1∑*1∪0∪1{ω|ω以相同的字符开始和结束}(0∪ε)1*01*∪1*说明：(0∪ε)表示语言{0,ε}(0∪ε)(1∪ε){ε,0,1,01}1*φφφ*{ε}说明：*运算只能把0个字符串连接在一起，得到的唯一的一个字符串是ε第9页，共35页，2023年，2月20日，星期六4/21/202312:32AM/10例题4：设R是任意的正则表达式，有下述恒等式成立。几个正则表达式的恒等式这些恒等式有助于对正则表达式定义的理解R∪φ=R空语言加上任何一个语言不改变这个语言Roε=R空串加上任何一个字符串上不改变这个字符串但是：R∪ε不一定等于R，Roφ不一定等于R第10页，共35页，2023年，2月20日，星期六4/21/202312:32AM/11例题5：程序设计语言中的基本单位称为单字，如变量名和常量，这些东西可以用正则表达式描述。通常是包括小数部分和正负号的的数值常量可以描述成下述语言的一个成员：{+,--,ε}(DD*∪DD*.D*∪D*.DD*)其中，D＝{0,1,2,…,9}，则72，3.14,+7.和-.01是该语言的字符串。在编译中，只要程序设计语言中的单字的语法用正则表达式描述出来，自动系统能够生成词法分析程序。这是编译程序的一部分，用来在开始阶段处理输入程序。第11页，共35页，2023年，2月20日，星期六4/21/202312:32AM/12第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式第12页，共35页，2023年，2月20日，星期六4/21/202312:32AM/13定理1：一个语言是正则的，当且仅当可以用正则表达式描述它。第13页，共35页，2023年，2月20日，星期六4/21/202312:32AM/14第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式第14页，共35页，2023年，2月20日，星期六4/21/202312:32AM/15引理1如果一个语言可以用正则表达式描述，则它是正则的。证明：考虑正则表达式R定义的6种情况(1)R=a,这里a是字母表∑中的一个元素，那么L(R)={a},下述NFA识别L(R)(注意：这台机器符合NFA的定义，但是不符合DFA的定义，因为(1)…(2)…)形式的表示，N=({q1,q2},∑,δ,q1,{,q2}),其中δ

的定义为δ(q1,a)=q2δ(q1,b)=φ,若第15页，共35页，2023年，2月20日，星期六4/21/202312:32AM/16R=ε；下述NFA识别L(R)R=φ；那么L(R)=φ,下述NFA识别L(R)(R1∪R2)，这里R1和R2是正则表达式；(R1oR2)，这里R1和R2是正则表达式；(R1*)，这里R1是正则表达式；(4)、(5)、(6)三种情况由正则语言类在正则运算下的封闭性的证明中给出的构造证明方法，很容易得出需要的NFA。第16页，共35页，2023年，2月20日，星期六4/21/202312:32AM/17例题6：分若干阶段把正则表达式(ab∪a)*转换成NFA，从最小的子表达式到大一点到大一点的子表达式逐步建立。使用构造证明中的方法一般不能给出状态最少的NFA。a和b(1)第17页，共35页，2023年，2月20日，星期六4/21/202312:32AM/18ab(2)ab∪a(3)第18页，共35页，2023年，2月20日，星期六4/21/202312:32AM/19(ab∪a)*(4)思考：本例题一共给出了8个状态，而最小的表示该表达式的NFA，只要2个状态，怎么表示？习题：把正则表达式(a∪b)*aba转换成一台NFA。请一步步根据步骤给出。第19页，共35页，2023年，2月20日，星期六4/21/202312:32AM/20第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式第20页，共35页，2023年，2月20日，星期六4/21/202312:32AM/21引理2如果一个语言是正则的，那么它可以用正则表达式描述。第21页，共35页，2023年，2月20日，星期六4/21/202312:32AM/22第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式第22页，共35页，2023年，2月20日，星期六4/21/202312:32AM/23广义非确定型有穷自动机GNFA第23页，共35页，2023年，2月20日，星期六4/21/202312:32AM/24GNFA其实就是NFA，只是转移箭头可以用任何正则表达式作标号，而不是只能用字母和ε做标号。GNFA读入输入符号段，而不必一次值读一个符号。GNFA是非确定性的，有几种不同的方式处理同一个符号串第24页，共35页，2023年，2月20日，星期六4/21/202312:32AM/25对GNFA的一些特殊要求：起始状态有射到其他每一个状态的箭头，但是没有从其他任何状态射入的箭头有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到其他任何状态的箭头；除起始状态和接受状态外，每一个状态到自身或其他状态都有一个箭头。第25页，共35页，2023年，2月20日，星期六4/21/202312:32AM/26DFA能够很容易的转化成这种特殊形式的GNFA添加一个新的起始状态和一个新的接受状态；从新的起始状态到老的起始状态有一个ε箭头；从每一个老的接受状态到新接受状态有一个ε箭头；如果一个箭头有多个标记(即两个状态之间有多个方向相同的箭头)，则把它替换为一个标记着原先标记的并集的箭头；在没有箭头的状态之间添加φ标记。(此步骤不改变识别的语言，因为φ标记的箭头永远不能被使用)第26页，共35页，2023年，2月20日，星期六4/21/202312:32AM/27第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式第27页，共35页，2023年，2月20日，星期六4/21/202312:32AM/28第一步：每一个GNFA都有一个等价的仅2个状态的GNFA每一个GNFA都有个状态(证明：GNFA都有起始状态和接受状态，且是两个不同的状态)每一个个状态的GNFA都可以转为为等价的状态的GNFA(如何转变才是本部分的关键所在)第28页，共35页，2023年，2月20日，星期六4/21/202312:32AM/29第二步：仅2个状态的GNFA，可以很容易的转换成为正则表达式证明：因为只有起始状态和接受状态两个状态，因此，只有一个从起始状态到接受状态的转移箭头，这个箭头上的标记就是等价的正则表达式。解决这个关键环节：当k>2时，如何构造等价的少一个状态的GNFA第29页，共35页，2023年，2月20日，星期六4/21/202312:32AM/30基本思路：任选一个不是起始状态和接受状