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

1、形式语言与自动机授课 人： 王 良 民MAIL:8/11/2022 12:28 PM1第六章 正则表达式6.1 引例6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/11/2022 12:28 PM2例题1：算术表达式：(5+4)2, 值为18，是一个数字正则表达式：(01)0*, 正则表达式的值是一个语言注意：(01)0* 表示的是01后加任意多个0构成的字符串所组成的语言0和1是集合0和1的缩写，就是01, 这部分的

2、值是语言0, 10*就是0*,其值为所有包含任意个0的字符串构成的语言在正则表达式中省略了连结运算符号o, (01)0*实际上是(01) o0*正则表达式可以用来描述满足“某种模式”的字符串。8/11/2022 12:28 PM3 很多应用程序及现代程序设计语言、文本编辑程序都提供用正则表达式描述模式的手段。例题2：正则表达式(01)*其值为：由0和1的所有字符串组成的语言，也表示为0, 1*表示方法：记为字母表，也可以表示该字母表中所有长度为1的字符串，而*为由该字母表中所有字符串组成的语言。如：(0*)(*1)表示所有以0开头而以1结尾的字符串正则运算的优先级：先星号，后连结，最后并，要改

3、变这种惯常的顺序需要用括号。8/11/2022 12:28 PM4第六章 正则表达式6.1 引例6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/11/2022 12:28 PM5定义 称R是一个正则表达式，如果R是a, 这里a是字母表中的一个元素；(R1R2)，这里R1和R2是正则表达式；(R1oR2)，这里R1和R2是正则表达式；(R1*)，这里R1是正则表达式；8/11/2022 12:28 PM6说明：在(1)和

4、(2)中，a和分别表示 a 和在(3)条中，表示空语言在第(4)、(5)、(6)表示通过正则运算并、连结和星号获得正则表达式（用较小的正则表达式定义较大的正则表达式，是归纳定义中的归纳步骤）此处和的区别：有一个空语句的语言，和空语言要想明显的区分正则表达式R和它所表示的语言时，后者用L(R)表示。8/11/2022 12:28 PM7第六章 正则表达式6.1 引例6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/11/2

5、022 12:28 PM8例题3：在下面的句子中，字母表为0,18/11/2022 12:28 PM9例题4：设R是任意的正则表达式，有下述恒等式成立。几个正则表达式的恒等式这些恒等式有助于对正则表达式定义的理解R = R空语言加上任何一个语言不改变这个语言Ro = R空串加上任何一个字符串上不改变这个字符串但是：R不一定等于R，Ro不一定等于R8/11/2022 12:28 PM10例题5：程序设计语言中的基本单位称为单字，如变量名和常量，这些东西可以用正则表达式描述。通常是包括小数部分和正负号的的数值常量可以描述成下述语言的一个成员：+, -, (DD*DD*. D*D*.DD*)其中，D

6、 0, 1, 2, , 9，则72，3.14, +7.和 -.01是该语言的字符串。在编译中，只要程序设计语言中的单字的语法用正则表达式描述出来，自动系统能够生成词法分析程序。这是编译程序的一部分，用来在开始阶段处理输入程序。 8/11/2022 12:28 PM11第六章 正则表达式6.1 引例6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/11/2022 12:28 PM12定理1：一个语言是正则的，当且仅当可以用

7、正则表达式描述它。8/11/2022 12:28 PM13第六章 正则表达式6.1 引例6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/11/2022 12:28 PM14引理1 如果一个语言可以用正则表达式描述，则它是正则的。证明：考虑正则表达式R定义的6种情况(1) R = a, 这里a是字母表中的一个元素，那么L(R)= a, 下述NFA识别L(R)(注意：这台机器符合NFA的定义，但是不符合DFA的定义，因为(

8、1) (2)形式的表示，N = (q1,q2, , , q1, ,q2 ), 其中 的定义为 (q1, a) = q2 (q1, b) =, 若8/11/2022 12:28 PM15R =；下述NFA识别L(R)R =；那么L(R)= , 下述NFA识别L(R)(R1R2)，这里R1和R2是正则表达式；(R1oR2)，这里R1和R2是正则表达式；(R1*)，这里R1是正则表达式；(4)、(5)、(6)三种情况由正则语言类在正则运算下的封闭性的证明中给出的构造证明方法，很容易得出需要的NFA。8/11/2022 12:28 PM16例题6：分若干阶段把正则表达式(aba)*转换成NFA，从最小

9、的子表达式到大一点到大一点的子表达式逐步建立。使用构造证明中的方法一般不能给出状态最少的NFA。 a和b (1) 8/11/2022 12:28 PM17 ab (2) aba (3) 8/11/2022 12:28 PM18(aba)* (4) 思考：本例题一共给出了8个状态，而最小的表示该表达式的NFA，只要2个状态，怎么表示？习题：把正则表达式(ab)*aba转换成一台NFA。请一步步根据步骤给出。8/11/2022 12:28 PM19第六章 正则表达式6.1 引例6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6

10、.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/11/2022 12:28 PM20引理2 如果一个语言是正则的，那么它可以用正则表达式描述。8/11/2022 12:28 PM21第六章 正则表达式6.1 引例6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/11/2022 12:28 PM22广义非确定型有穷自动机GNFA8/11/2022 12:28 PM23

11、GNFA其实就是NFA，只是转移箭头可以用任何正则表达式作标号，而不是只能用字母和做标号。GNFA读入输入符号段，而不必一次值读一个符号。GNFA是非确定性的，有几种不同的方式处理同一个符号串 8/11/2022 12:28 PM24对GNFA的一些特殊要求：起始状态有射到其他每一个状态的箭头，但是没有从其他任何状态射入的箭头有唯一的一个接受状态，并且它有从其它每一个状态射入的箭头，但是没有射到其他任何状态的箭头；除起始状态和接受状态外，每一个状态到自身或其他状态都有一个箭头。8/11/2022 12:28 PM25DFA能够很容易的转化成这种特殊形式的GNFA添加一个新的起始状态和一个新的接

12、受状态；从新的起始状态到老的起始状态有一个箭头；从每一个老的接受状态到新接受状态有一个箭头；如果一个箭头有多个标记(即两个状态之间有多个方向相同的箭头)，则把它替换为一个标记着原先标记的并集的箭头；在没有箭头的状态之间添加标记。(此步骤不改变识别的语言，因为标记的箭头永远不能被使用)8/11/2022 12:28 PM26第六章 正则表达式6.1 引例6.2 正则表达式的形式定义6.2.1形式定义6.2.2 例题6.3 正则表达式与有穷自动机的等价性6.3.1充分性证明6.3.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式8/11/2022 12

13、:28 PM27第一步：每一个GNFA都有一个等价的仅2个状态的GNFA每一个GNFA都有个状态(证明：GNFA都有起始状态和接受状态，且是两个不同的状态)每一个个状态的GNFA都可以转为为等价的状态的GNFA(如何转变才是本部分的关键所在)8/11/2022 12:28 PM28第二步：仅2个状态的GNFA，可以很容易的转换成为正则表达式证明：因为只有起始状态和接受状态两个状态，因此，只有一个从起始状态到接受状态的转移箭头，这个箭头上的标记就是等价的正则表达式。解决这个关键环节：当k 2时，如何构造等价的少一个状态的GNFA8/11/2022 12:28 PM29基本思路：任选一个不是起始状态和接受状态的中间状态，将其删除，记为q删除并通过修改留下来的部分，使其仍然识别相同的语言。(这个q删除一定能找到吗？) 删除q删除后，改动每一个留下来的箭头上标记的正则表达式。新标记中加入失去的计算，从而弥补由于删除来的损失。从状态qi到qj的新标记是描述使机器直接从从状态qi到qj或通过状态q删除带到qj的所有字符串的表达式。图示给出了一个例子：8/11/2022 12:28 PM30思考题：如何形式化的描述GNFA? 如何形式化证明上述定理？ 8/11/202