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

8/13/20243:15PM/1第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/13/20243:15PM/2例题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*正则表达式可以用来描述满足“某种模式”的字符串。8/13/20243:15PM/3

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

6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/13/20243:15PM/8例题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个字符串连接在一起，得到的唯一的一个字符串是ε8/13/20243:15PM/9例题4：设R是任意的正则表达式，有下述恒等式成立。几个正则表达式的恒等式这些恒等式有助于对正则表达式定义的理解R∪φ=R空语言加上任何一个语言不改变这个语言Roε=R空串加上任何一个字符串上不改变这个字符串但是：R∪ε不一定等于R，Roφ不一定等于R8/13/20243:15PM/10例题5：程序设计语言中的基本单位称为单字，如变量名和常量，这些东西可以用正则表达式描述。通常是包括小数部分和正负号的的数值常量可以描述成下述语言的一个成员：{+,--,ε}(DD*∪DD*.D*∪D*.DD*)其中，D＝{0,1,2,…,9}，则72，3.14,+7.和-.01是该语言的字符串。在编译中，只要程序设计语言中的单字的语法用正则表达式描述出来，自动系统能够生成词法分析程序。这是编译程序的一部分，用来在开始阶段处理输入程序。8/13/20243:15PM/11第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/13/20243:15PM/12定理1：一个语言是正则的，当且仅当可以用正则表达式描述它。8/13/20243:15PM/13第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/13/20243:15PM/14引理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)=φ,若8/13/20243:15PM/15R=ε；下述NFA识别L(R)R=φ；那么L(R)=φ,下述NFA识别L(R)(R1∪R2)，这里R1和R2是正则表达式；(R1oR2)，这里R1和R2是正则表达式；(R1*)，这里R1是正则表达式；(4)、(5)、(6)三种情况由正则语言类在正则运算下的封闭性的证明中给出的构造证明方法，很容易得出需要的NFA。8/13/20243:15PM/16例题6：分若干阶段把正则表达式(ab∪a)*转换成NFA，从最小的子表达式到大一点到大一点的子表达式逐步建立。使用构造证明中的方法一般不能给出状态最少的NFA。a和b(1)8/13/20243:15PM/17ab(2)ab∪a(3)8/13/20243:15PM/18(ab∪a)*(4)思考：本例题一共给出了8个状态，而最小的表示该表达式的NFA，只要2个状态，怎么表示？习题：把正则表达式(a∪b)*aba转换成一台NFA。请一步步根据步骤给出。8/13/20243:15PM/19第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/13/20243:15PM/20引理2如果一个语言是正则的，那么它可以用正则表达式描述。8/13/20243:15PM/21第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/13/20243:15PM/22广义非确定型有穷自动机GNFA8/13/20243:15PM/23GNFA其实就是NFA，只是转移箭头可以用任何正则表达式作标号，而不是只能用字母和ε做标号。GNFA读入输入符号段，而不必一次值读一个符号。GNFA是非确定性的，有几种不同的方式处理同一个符号串8/13/20243:15PM/24对GNFA的一些特殊要求：起始状态有射到其他每一个状态的箭头，但是没有从其他任何状态射入的箭头有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到其他任何状态的箭头；除起始状态和接受状态外，每一个状态到自身或其他状态都有一个箭头。8/13/20243:15PM/25DFA能够很容易的转化成这种特殊形式的GNFA添加一个新的起始状态和一个新的接受状态；从新的起始状态到老的起始状态有一个ε箭头；从每一个老的接受状态到新接受状态有一个ε箭头；如果一个箭头有多个标记(即两个状态之间有多个方向相同的箭头)，则把它替换为一个标记着原先标记的并集的箭头；在没有箭头的状态之间添加φ标记。(此步骤不改变识别的语言，因为φ标记的箭头永远不能被使用)8/13/20243:15PM/26第六章正则表达式6.1引例6.2正则表达式的形式定义6.2.1形式定义6.2.2例题 6.3正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/13/20243:15PM/27第一步：每一个GNFA都有一个等价的仅2个状态的GNFA每一个GNFA都有个状态(证明：GNFA都有起始状态和接受状态，且是两个不同的状态)每一个个状态的GNFA都可以转为为等价的状态的GNFA(如何转变才是本部分的关键所在)8/13/20243:15PM/28第二步：仅2个状态的GNFA，可以很容易的转换成为正则表达式证明：因为只有起始状态和接受状态两个状态，因此，只有一个从起始状态到接受状态的转移箭头，这个箭头上的标记就是等价的正则表达式。解决这个关键环节：当k>2时，如何构造等价的少一个状态的GNFA8/13/20243:15PM/29基本思路：任选一个不是起始状态和接受状态的中间状态，将其删除，记为q删除并通过修改留下来的部分，使其仍然识别相同的语言。(这个q删除一定能找到吗？)

删除q删除后，改动每一个留下来的箭头上标记的正则表达式。新标记中加入失去的计算，从而弥补由于删除来的损失。从状态qi到qj的新标记是描述使机器直接从从状态qi到qj或通过状态q删除带到qj的所有字符串的表达式。图示给出了一个例子：8/13/20243:15PM/30思考题：